문자열 매칭 선택 기준

KMP와 롤링 해시는 모두 선형에 가깝게 찾지만, 실패 처리와 충돌 리스크를 관리하는 방식이 다릅니다.

정확 매칭

접두사 함수로 되돌아간다

KMP는 비교 실패 시 이미 맞은 접두사 정보를 써서 텍스트 인덱스를 되돌리지 않습니다.

대량 비교

여러 구간을 빠르게 비교해야 하면 이전 해시에서 앞 문자를 빼고 뒤 문자를 더합니다.

충돌 위험

단일 해시가 같아도 문자열이 다를 수 있으므로 이중 해시나 실제 비교를 붙입니다.

KMP 패턴 하나를 정확히 찾고 충돌 허용이 없을 때 안정적입니다.

롤링 해시 부분 문자열 비교가 많거나 후보 위치를 빠르게 거를 때 유리합니다.

최종 점검 패턴 길이 1, 겹치는 패턴, 매우 긴 반복 문자열을 넣어 봅니다.