선택 이유와 실패 반례를 함께 남긴다
KMP와 롤링 해시는 모두 빠르지만 실패 처리와 충돌 리스크가 다릅니다. 제출 전에는 선택 이유, 검증 장치, 경계 테스트를 한 번에 확인합니다.
증거
확인할 규칙
통과 기준
KMP
불일치 시
j = pi[j - 1]로만 이동
겹친 패턴과 패턴=텍스트를 모두 찾음
롤링 해시
앞 문자 제거 뒤 음수 보정
길이 고정 창에서
O(1) 갱신최종 검증
해시 일치를 바로 정답으로 확정하지 않음
이중 해시 또는 원문 비교로 오탐 제거
테스트
드러나는 실수
통과 기준
aaaaa / aaaKMP 겹친 매칭 누락
시작 위치
0, 1, 2를 모두 찾음완전 불일치
불필요한 재스캔 또는 잘못된 해시 후보
후보 없음과 시간복잡도 유지
충돌 민감 입력
해시 일치만으로 오탐 확정
원문 비교 또는 이중 해시로 최종 확인