정확성 고정
정확성
높음
확장성
중간
한 패턴의 위치를 빠짐없이 찾아야 할 때 우선합니다.
빠른 후보 필터와 정답 확정을 분리한다
KMP는 결정적 정확성에 강하고, 롤링 해시는 반복 후보 비교를 줄입니다. 해시를 선택하면 충돌 검증 비용을 별도 항목으로 계산해야 합니다.
후보 수 절감
반복비교
강함
충돌관리
필요
같은 길이 부분문자열을 많이 비교할 때 자연스럽습니다.
충돌 확률 완화
안정성
상승
상수비용
증가
충돌 민감 문제에서 단일 해시보다 안전한 기본값입니다.
정답 확정
오탐제거
확실
비교비용
추가
해시 후보를 원문 비교로 확인할 때 최종 정확성이 확보됩니다.
문제 조건
우선 선택
판정 근거
단일 패턴 정확 검색
KMP
충돌 없이
O(N+M)으로 위치 확정부분문자열 후보 대량 비교
롤링 해시
창마다 해시를 갱신해 후보 수를 먼저 절감
오탐 비용이 큼
이중 해시 + 직접 비교
충돌 확률과 최종 오탐을 함께 줄임