정확 매칭인가
한 패턴의 실제 위치를 빠짐없이 찾아야 하면 결정적 알고리즘을 우선합니다.
선택 흐름 지도
정확성, 후보 수, 충돌 리스크 순서 선택
문자열 매칭은 알고리즘 이름보다 요구 조건을 먼저 고정해야 합니다. 단일 패턴이면 KMP, 많은 구간 비교면 해시, 충돌 민감 환경이면 검증을 붙입니다.
후보가 많은가
같은 길이 구간을 반복 비교하면 해시로 후보를 먼저 줄입니다.
충돌에 민감한가
해시 일치만으로 확정하지 말고 이중 해시나 직접 비교를 붙입니다.
상수 비용 검토
검증 비용이 커지면 KMP, 해시, 다중 패턴 알고리즘을 다시 나눕니다.
단일 패턴 정확 검색
KMP가 기본 선택입니다. 접두사 함수로 불일치 이후 위치를 결정적으로 건너뜁니다.
KMP
O(N+M)
대량 구간 후보 비교
롤링 해시가 자연스럽습니다. 창 이동마다 해시를 갱신해 비교량을 줄입니다.
rolling hash
O(1) update
오탐 비용이 큰 문제
해시가 같을 때 문자열을 직접 비교하거나 두 해시를 함께 써서 리스크를 낮춥니다.
verify
double hash
해시를 쓰는 순간 “빠른 후보 필터”와 “정답 확정”을 분리하세요. KMP는 정답 확정까지 결정적이고, 해시는 검증 단계를 붙일 때 안정적입니다.