같은 문자열도 질문에 따라 다른 패턴이 보입니다
연속된 부분을 찾는지, 순서만 맞는 문자들을 고르는지부터 구분하세요. 작은 문자열에서 직접 예상한 뒤 각 알고리즘이 비교를 줄이는 방식을 따라가 봅니다.
툴허브 편집 ·
불일치 뒤에도 남는 접두사 찾기
ABAB처럼 앞뒤가 겹치는 패턴을 생각해 보세요. 비교에 실패한 지점에서 이미 일치한 부분을 얼마나 재사용하는지 접두사 표와 맞춰 봅니다.
KMP 패턴 매칭 열기 →창을 한 칸 밀 때 해시 갱신하기
길이가 같은 이웃 구간은 첫 문자가 빠지고 새 문자 하나가 들어옵니다. 해시가 일치한 후보도 실제 문자들이 같은지 마지막으로 확인해야 합니다.
라빈-카프 열기 →공통 접두사가 끝나는 가지 찾기
car와 cat를 넣으면 c, a까지 경로를 공유하고 세 번째 글자에서 갈라집니다. 단어 하나가 다른 단어의 접두사일 때는 끝 표시가 왜 필요한지도 보세요.
트라이 열기 →접미사를 정렬하면 가까워지는 문자열 보기
banana의 각 위치에서 시작하는 접미사를 적어 보세요. 정렬 후 ana로 시작하는 후보가 붙어 있어 특정 패턴이 나타나는 위치를 찾기 쉬워집니다.
접미사 배열 열기 →연속하지 않아도 되는 공통 문자 찾기
ABC와 AC의 최장 공통 부분 수열은 AC입니다. 중간 문자를 건너뛰어도 되지만 순서는 바꿀 수 없다는 조건을 표의 값과 대조하세요.
LCS (최장 공통 부분수열) 열기 →한 글자 바꾼 비용을 표에서 찾기
cat을 cut으로 바꿀 때는 한 글자 치환이면 됩니다. 각 칸에서 삽입, 삭제, 치환 중 어느 직전 칸을 참조하는지 살펴보세요.
편집 거리 열기 →겹치는 구간의 합 다시 쓰기
1, 4, 2, 7에서 길이 3 창을 오른쪽으로 밀면 1이 빠지고 7이 들어옵니다. 이전 합 7에서 두 변화만 반영하면 다음 합은 13입니다.
슬라이딩 윈도우 열기 →잦은 기호가 짧은 코드로 가는 과정 보기
드물게 나오는 두 기호를 먼저 묶고 빈도를 더해 다시 후보에 넣어 보세요. 완성된 트리에서 각 기호까지 경로 길이를 실제 빈도와 비교합니다.
허프만 코딩 열기 →