KMP prefix table

불일치해도 텍스트는 되돌리지 않는다

패턴 ababd에서 네 글자까지 맞고 실패하면, 이미 맞은 접두/접미 길이 pi[3]=2로 패턴 포인터만 이동합니다.

패턴과 접두사 함수

pattern
a b a b d
pi
0 0 1 2 0

abab까지 맞은 상태의 다음 비교는 d지만 텍스트 문자가 c라 실패합니다.

실패 순간의 점프

text
a b a b c
move

i는 현재 위치 유지, j = pi[j - 1]로 4 -> 2만 이동

text i 유지 pattern j 점프 전체 O(N+M)
1 pi 계산

패턴 내부의 접두사와 접미사 일치 길이를 저장합니다.

2 텍스트 스캔

텍스트 인덱스는 왼쪽에서 오른쪽으로만 전진합니다.

3 실패 점프

불일치하면 패턴 포인터만 접두사 함수 값으로 이동합니다.

4 위치 기록

패턴 길이만큼 맞으면 시작 인덱스 10을 기록합니다.