패턴의 현재 문자와 일치하지 않을 때 KMP는 왜 패턴을 처음부터 다시 비교하지 않나요?

처음부터 다시 비교하지 않는 이유는 불일치 전까지 읽은 텍스트의 끝에 이미 패턴의 더 짧은 접두가 남아 있다는 사실을 π가 알려 주기 때문입니다. 현재 패턴 상태를 j라고 하면, p[0..j-1]과 텍스트의 끝이 일치한 상태에서 p[j]가 다를 때 다음 후보는 j-1이 아니라 π[j-1]입니다. 이 길이는 현재 일치 구간의 가장 긴 proper border이므로, 그보다 긴 후보는 이미 불가능하다고 증명되어 있습니다. 그 상태에서 같은 텍스트 문자를 다시 비교합니다.

예를 들어 패턴 ababaca와 텍스트 접미 ab abab를 생각해 보겠습니다. ababa까지 읽은 상태는 j=5이고 다음 입력이 b라면 p[5]=c와 불일치합니다. j=π[4]=3으로 내리면 이미 읽은 끝의 aba가 패턴 앞의 aba와 같다는 사실을 재사용할 수 있고, 같은 b를 p[3]=b와 비교해 j=4가 됩니다. 이때 텍스트 인덱스는 뒤로 가지 않습니다. 다시 실패하면 j=π[3]으로 더 짧은 border를 시험합니다. 각 fallback은 이미 증명된 접두-접미 관계를 소비하므로 전체 증가와 감소 횟수가 선형으로 제한됩니다.

π는 trie의 부모 경로와 다릅니다. trie는 여러 키의 접두 경로를 저장하지만 KMP의 fallback은 하나의 패턴에서 suffix와 prefix가 겹치는 위치를 저장합니다. 완전 일치 뒤에도 j=π[m-1]로 내려가야 ababa 안의 겹치는 aba를 찾을 수 있습니다.

구현을 검증할 때는 j를 어떻게 초기화하고 어떤 인덱스를 읽는지까지 기록하면 좋습니다. 현재 j가 4라는 것은 패턴의 인덱스 0부터 3까지가 이미 일치했다는 뜻이므로, 다음 비교 대상은 p[4]입니다. 이 문자가 다르면 p[0..3] 전체를 버리고 p[0..π[3]-1]을 남깁니다. π[3]은 현재 일치한 문자열의 suffix이면서 패턴 prefix이므로, 그 뒤에 같은 텍스트 문자를 붙일 가능성이 있는 유일한 최대 후보입니다. 이 후보도 실패하면 그 후보의 border로 반복해서 내려갑니다.

검증할 때는 단순히 결과 위치만 보지 않고 비교 횟수와 상태 전이를 함께 봅니다. aaaaab 같은 패턴과 aaaaaaaa... 같은 텍스트는 naive 구현의 재비교를 드러내고, KMP에서는 텍스트 인덱스가 뒤로 가지 않는지 확인할 수 있습니다. 다만 입력이 아주 짧거나 패턴이 반복되지 않는다면 두 구현의 결과만 보고 내부 동작이 맞다고 단정하기 어렵습니다.