KMP는 확정 탐색, 해시는 후보 필터링에 강하다
문자열 문제는 단일 패턴의 모든 위치를 정확히 찾는지, 많은 부분문자열 후보를 빠르게 비교해야 하는지에 따라 도구가 달라집니다.
접두/접미 재사용
pi[i]로 일치한 접두사 길이를 재사용해 텍스트 포인터를
되돌리지 않고 O(N+M)에 찾습니다.
창 값을 빠르게 갱신
base와 mod로 부분문자열 값을 굴리며 길이가 같은 후보를 O(1)에 가깝게 거릅니다.
해시 충돌 검증
해시가 같아도 원문 직접 비교나 이중 mod 해시로 collision 오탐을 줄입니다.
문제 조건에 맞춰 조합
다중 패턴 후보는 해시로 줄이고, 최종 위치 검증은 문자열 비교나 KMP로 확정할 수 있습니다.