ababcabcabababd
기준 문자열입니다.
증상, 원인, 반례를 한 줄로 묶어 디버깅한다
KMP는 j 이동, 롤링 해시는 모듈러 보정과 검증 누락에서
자주 틀립니다. 반례를 먼저 정하면 원인을 빠르게 좁힐 수 있습니다.
ababd
찾을 패턴입니다.
index 10
정상 구현의 매칭 시작 위치입니다.
완전 매칭 뒤 j를 0으로 고정하면 겹치는 패턴을
건너뜁니다.
aaaaa에서 aaa를 찾고
j = pi[j - 1]로 이어 갑니다.
윈도우에서 앞 문자를 뺀 값이 음수가 되면 같은 문자열도 달라집니다.
(x - y + mod) % mod로 매번 보정합니다.
단일 해시 일치만 보고 위치를 반환하면 충돌 입력에서 틀립니다.
이중 해시나 원문 비교로 후보를 한 번 더 확인합니다.
겉보기 같은 유니코드 문자열도 코드포인트 구성이 다를 수 있습니다.
검색 전 소문자화, 정규화, 공백 정책을 같은 순서로 적용합니다.