불일치 후 점프
불일치하면 텍스트 인덱스는 유지하고 j = pi[j - 1]로만
되돌린다.
문자열 매칭 디버깅
KMP는 j 이동, 롤링 해시는 모듈러 보정과 최종 검증에서
실수가 가장 자주 발생합니다.
기준 검색
text
ababcabcabababd
pattern
ababd
match
index 10
윈도우 갱신
왼쪽 문자를 뺀 뒤 음수가 되지 않게 보정하고 오른쪽 문자를 더한다.
정답 확정
해시가 같아도 직접 비교나 이중 해시 없이 매칭으로 확정하지 않는다.
매칭 누락
완전 매칭 뒤 j를 0으로 고정하면 겹치는 패턴을 놓친다.
aaaaa에서 aaa를 찾아 확인한다.
해시 음수
윈도우에서 왼쪽 문자를 뺀 값이 음수이면 같은 문자열도 다른 해시가 된다.
(x - y + mod) % mod 형태로 보정한다.
오탐 확정
단일 해시 일치만 보고 위치를 반환하면 충돌 입력에서 틀릴 수 있다.
해시 후보를 원문 비교로 한 번 더 확인한다.