KMP란?
KMP(Knuth-Morris-Pratt)는 긴 텍스트에서 패턴 문자열이 나타나는 위치를 O(n+m)에 찾는 문자열 검색 알고리즘입니다. 한 글자씩 밀며 매번 처음부터 비교하는 단순 검색의 O(nm) 비효율을, "이미 비교해서 알아낸 정보"를 재활용해 없앱니다.
핵심 한 줄: "불일치해도 텍스트를 되돌리지 않는다." 패턴만 적절한 만큼 점프시키면 됩니다.
핵심: 실패 함수(부분 일치 테이블)
패턴 자기 자신을 분석해, 각 위치마다 "접두사이면서 동시에 접미사인 가장 긴 부분의 길이(LPS)"를 미리 구해 둡니다.
패턴 도중 불일치가 나면, 이 LPS 값만큼 패턴을 앞으로 점프시킵니다. 이미 일치했던 접두사가 다시 쓰일 수 있는 위치로 정확히 옮기는 것이라, 비교를 처음부터 다시 하지 않아도 됩니다.
왜 빨라지나?
단순 검색은 불일치할 때마다 텍스트 포인터를 한 칸 뒤로 물려 다시 시작합니다. KMP는 텍스트 포인터를 절대 되돌리지 않고 앞으로만 갑니다 — 되돌릴 정보를 실패 함수가 이미 담고 있기 때문입니다. 그래서 텍스트를 딱 한 번 훑어 O(n)이 되고, 실패 함수 계산이 O(m)이라 전체 O(n+m)입니다.
동작 원리
1단계. 패턴으로 실패 함수(LPS) 배열을 만듭니다.
2단계. 텍스트를 한 번 훑으며 패턴과 비교합니다.
3단계. 글자가 일치하면 텍스트·패턴 포인터를 둘 다 전진시킵니다.
4단계. 불일치하면 패턴 포인터를 LPS값으로 점프시키고(텍스트 포인터는 그대로), 패턴이 처음이면 텍스트만 한 칸 전진합니다.
5단계. 패턴 끝까지 일치하면 한 번 발견한 것이며, 다시 LPS로 점프해 다음 출현을 찾습니다.
알고노트 시각화는 불일치 시 패턴이 어디로 점프하는지, 텍스트 포인터가 그대로인지를 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n + m) |
| 공간 | O(m) |
n은 텍스트 길이, m은 패턴 길이입니다.
예시로 따라가기
텍스트 ABABABCA, 패턴 ABABC:
- •
ABAB까지 일치하다CvsA에서 불일치 - •단순 검색이면 텍스트를 되돌려 다시 시작하지만, KMP는 LPS를 보고 패턴만 점프
- •이미 일치한
AB를 재활용해 텍스트 포인터는 그대로 유지하고 계속 진행
자주 하는 실수
- •실패 함수 오류: LPS 계산이 KMP의 절반입니다. "진접두사 = 진접미사"의 최대 길이임을 정확히 구현하세요.
- •텍스트 되돌리기: 텍스트 포인터를 뒤로 물리면 O(nm)으로 퇴화합니다 — KMP의 의미가 사라집니다.
- •점프 후 처리: 패턴 포인터가 0인데도 불일치면 텍스트만 전진시켜야 무한 루프를 피합니다.
알고노트에서 직접 확인하세요
불일치가 났을 때 패턴이 실패 함수만큼 점프하고, 텍스트 포인터는 되돌아가지 않는 과정을 알고노트에서 단계별로 확인할 수 있습니다.