문자열 매칭 첫 판단

정확 위치는 KMP, 많은 후보 비교는 롤링 해시

문제를 보자마자 정확성 요구, 반복 비교 수, 충돌 허용 여부를 분리하면 어떤 알고리즘을 먼저 잡을지 바로 정해집니다.

KMP

한 패턴의 실제 위치를 결정적으로 찾는다

접두사 함수 pi로 이미 맞춘 길이를 재사용해 텍스트 포인터를 되돌리지 않습니다.

O(N+M) 충돌 없음 단일 패턴
Rolling Hash

같은 길이 구간 후보를 빠르게 걸러낸다

창을 한 칸 밀 때 이전 해시에서 앞 문자를 빼고 뒤 문자를 더해 비교 후보를 줄입니다.

O(1) update 후보 필터 검증 필요
1 정확 위치가 필수인가

오탐이 허용되지 않으면 KMP를 기본 선택으로 둡니다.

2 후보 비교가 반복되는가

부분문자열 후보가 많으면 해시로 먼저 좁힙니다.

3 해시 일치가 곧 정답인가

아니어야 합니다. 직접 비교나 이중 해시를 붙입니다.