라빈-카프 알고리즘 (Rabin-Karp Algorithm)

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm 참고

이 알고리즘 자체는 문자열 매칭 문제를 위한 알고리즘인데, 사실 문자열 매칭 문제 자체는 그냥 KMP를 쓰는 것이 낫다.

다만, 여기의 해싱 기법은 다른 응용 문제에서도 종종 유용하게 활용된다.

원본 알고리즘에서는, 해쉬가 같아도 문자열이 다를수도 있기 때문에, 진짜 문자열이 같은지도 비교를 한번 더 해보는 과정을 거친다. 그러다보니 문자열 매칭 문제에 적용할 경우 최악 경우에는 O(nm)의 복잡도가 나오는데, 이래서는 PS에서의 시간제한을 통과하지 못한다.

PS에서 쓰려면, 해쉬를 잘 골라서 그냥 해쉬만 비교해서 같으면 매치된다고 간주해야 한다. 그리고 테스트케이스에 반례가 없기를 기도해야 한다.

기본 아이디어는 s[i:j]에 대한 해시가 있을때 s[i+1:j+1]의 해시를 O(1)에 구하는 것이지만, O(|s|)의 전처리 과정을 걸치면, 임의의 s[x:y]의 해쉬를 O(1)에 구할수 있다.