by. Knuth, Morris and Pratt
불일치가 발생했을 경우, Text string의 앞부분에 어떤 문자가 있는 지를 미리 알고 있음.
⇒ 불일치가 발생한 앞 부분에 대해서는 다시 비교할 필요 없이 matching을 수행함.
Pattern을 전처리 → next[M]을 구해 잘못된 시작을 최소화함.
-
next[M]이란 불일치가 발생했을 경우 이동할 위치
-
p[0~i]의 접미사와 일치하는 최장 접두사의 끝자리에 위치함.
-
Example
시간 복잡도 : O(M+N)
