Rabin-Karp Fingerprinting이란?
긴 String을 Hashing해서 사용할 때 쓰는 알고리즘이다.
k길이의 스트링 str[i, i+k-1]을 들여다 보면 k만큼의 시간이 걸린다.
그리고 나서 i+1부터 다시 k길이의 스트링을 들여다 보면 또 k만큼의 시간이 걸린다.
그럼 어떻게 할까?
hash를 재미있게 이용하면 된다.
hashing하는 function을 f()라고 하면
그니까 hashmap을 만들때 처음 k길이의 스트링에 대한 hash값을 만든다면 인덱스를 하나 옮긴 스트링의 hash를 에 구할 수 있다.
여기서 x값은 스트링 s에 들어오는 문자의 종류에 따라 설정하면 된다. 영어의 대소문자만 쓴다면 26+26 = 52개로 지정할 수도 있고, 아스키코드에 해당하는 문자열이 다 들어오는 경우 256으로 설정하면 되겠다. (문자 종류보다 적은 수로 x를 설정하면 확실히 collision이 미친듯이 일어나겠지...)
값은 엄청 커질수가 있으므로 mod 연산을 사용할 수 밖에 없다. 혹시라도 마이너스 연산에서 모드 할 때에는 MOD값을 더해주고 %MOD하는 것을 잊지말자~!
또 MOD값을 설정할 때는 당연히 큰 소수로... :D
끝.
'Algorithm > String' 카테고리의 다른 글
| Suffix Array O(NlgNlgN)과 O(NlgN) 구현 및 설명. (13) | 2017.06.11 |
|---|---|
| Suffix Array & LCP (C++11 Code Only) (0) | 2016.11.20 |
| 문자열 처리 알고리즘 - LCP (4) | 2016.11.20 |
| 문자열 처리 알고리즘 - Suffix Array (0) | 2016.11.20 |
| 문자열 처리 알고리즘 - KMP (2) | 2016.11.20 |
