단일 패턴, 후보 비교, 다중 패턴을 구분합니다.
요구 조건을 고정한 뒤 검증 장치를 붙인다
알고리즘 이름부터 고르지 말고, 단일 패턴인지 대량 후보 비교인지와 충돌 허용 여부를 먼저 체크합니다.
정확 위치가 필요하면 접두사 함수부터 검토합니다.
같은 길이 구간 비교가 많으면 해시로 후보를 줄입니다.
해시 일치 뒤 이중 해시나 원문 비교를 남깁니다.
반복 문자와 겹친 매칭으로 선택을 확인합니다.
상황
우선 선택
검증 장치
단일 패턴 검색
KMP로
O(N+M) 정확 매칭pi 경계와 중복 매칭 위치 확인부분문자열 대량 비교
롤링 해시로 후보를 빠르게 걸러냄
길이 고정과 모듈러 계산 순서 점검
충돌 불허
KMP 또는 해시 뒤 실제 문자열 비교
이중 해시와 원문 비교로 오탐 제거