====== 라빈-카프 알고리즘 (Rabin-Karp Algorithm) ======
  * [[https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm]] 참고
  * 이 알고리즘 자체는 문자열 매칭 문제를 위한 알고리즘인데, 사실 문자열 매칭 문제 자체는 그냥 KMP를 쓰는 것이 낫다.
  * 다만, 여기의 해싱 기법은 다른 응용 문제에서도 종종 유용하게 활용된다.
  * 원본 알고리즘에서는, 해쉬가 같아도 문자열이 다를수도 있기 때문에, 진짜 문자열이 같은지도 비교를 한번 더 해보는 과정을 거친다. 그러다보니 문자열 매칭 문제에 적용할 경우 최악 경우에는 O(nm)의 복잡도가 나오는데, 이래서는 PS에서의 시간제한을 통과하지 못한다.
  * PS에서 쓰려면, 해쉬를 잘 골라서 그냥 해쉬만 비교해서 같으면 매치된다고 간주해야 한다. 그리고 테스트케이스에 반례가 없기를 기도해야 한다.
  * 해쉬를 기본적인 [[https://en.wikipedia.org/wiki/Rabin_fingerprint|Rabin fingerprint]]를 쓸 것이고, 그렇다면 a와 모듈러를 어떻게 고르냐의 문제인데..
    * 모듈러는 가능한 큰 소수로 잡는 것이 좋다. ex) 1000000007, 1000000009
    * a는 너무 작지 않게, 그리고 모듈러의 원시근이면 좋다 ([[https://blog.encrypted.gg/857|출처]])
    * 그게 아니면, 여러개의 모듈로를 이용해 구한 해시를 이어붙이는 방법도 있다.
  * 기본 아이디어는 s[i:j]에 대한 해시가 있을때 s[i+1:j+1]의 해시를 O(1)에 구하는 것이지만, O(|s|)의 전처리 과정을 걸치면, 임의의 s[x:y]의 해쉬를 O(1)에 구할수 있다.