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