Pattern
한 패턴을 정확히 찾는지, 많은 구간과 패턴을 비교하는지부터 나눕니다.
string matching
KMP 롤링 해시 선택 기준
문자열 매칭에서 실패 함수와 해시 윈도우가 각각 어떤 상황에 유리한지 비교합니다.
선택 흐름
Prefix
KMP는 접두사 함수를 만들어 불일치 때 되돌아갈 위치를 계산합니다.
Window
롤링 해시는 같은 길이 구간의 해시를 빠르게 갱신합니다.
Collision
해시는 충돌 가능성이 있으므로 이중 해시나 실제 비교를 고려합니다.
Verify
오탐과 누락을 작은 입력, 반복 문자, 경계 위치에서 확인합니다.
판단 포인트
KMP
결과가 결정적이고 충돌이 없어서 단일 패턴 검색에 안정적입니다.
Rolling Hash
부분 문자열 비교가 많거나 여러 구간을 빠르게 비교할 때 유리합니다.
Double Hash
충돌 리스크를 낮추지만 모듈러와 곱셈 비용이 늘어납니다.
Fallback Compare
해시가 같을 때 실제 문자열을 비교하면 정확성을 점검할 수 있습니다.
Input Shape
같은 문자가 반복되는 문자열은 실패 함수와 해시 갱신 실수를 잘 드러냅니다.
문자열 알고리즘 선택은 빠른 이름 외우기가 아니라 충돌 허용 여부와 비교 횟수를 먼저 보는 일입니다.