KMP
접두사 함수로 이미 맞춘 정보를 재사용한다. 텍스트 포인터를 되돌리지 않아 단일 패턴 검색을 예측 가능하게 처리한다.
O(N+M)정확성 우선충돌 없음
STRING MATCHING
정확 매칭은 KMP, 대량 후보 비교는 롤링 해시
문자열 문제는 먼저 “한 패턴을 정확히 찾는가”와 “많은 구간을 빠르게 비교하는가”를 나누면 선택이 흔들리지 않는다.
Rolling Hash
고정 길이 창의 해시를 이동하면서 갱신한다. 반복 비교가 많을 때 후보를 빠르게 줄이고, 해시 일치 후 실제 문자열로 검증한다.
O(1) 갱신후보 필터충돌 검증
단일 패턴정확 위치 찾기는 KMP가 기본 선택
중복 구간부분문자열 후보가 많으면 해시가 자연스러움
안전 장치해시는 이중 해시나 직접 비교로 오탐 제거
판단 순서: 정확성 요구를 먼저 고정하고, 비교 횟수가
병목이면 해시를 조합한다.