목록2026/03/13 (1)
Elevation
문자열 - KMP
나는 문자열 알고리즘을 개인적으로 별로 좋아하지 않는데, 특히 kmp는 유난히 이해가 잘 되지 않아서 계속 글 쓰기를 미뤄놓고 있었다. 하지만 class 6에 kmp 문제가 등장하기도 하고 슬슬 한번쯤 다뤄야 할 주제인 것 같아 정리해 본다. KMP(Knuth-Morris-Pratt) 알고리즘은 단일 문자열 서칭에 있어 가장 강력한 알고리즘 중 하나이다. 문자열 $T$ 내에서, 찾아야 하는 대상인 패턴 문자열 $P$가 어디에 등장하는지 구하는 문제가 주어졌다고 가정해 보자. $T$의 모든 인덱스를 시작점으로 하여 패턴과의 일치 여부를 비교하는 경우 최악에는 두 문자열 길이의 곱인 $O(NM)$만에 동작할 것이다. 물론 $P$가 길지 않은 경우에는 큰 문제가 없으며 패턴과 일치하지 않는 순간 바로 brea..
ps/기타
2026. 3. 13. 14:01