라빈-카프 알고리즘

[1. 개요]

 

 

[2. 해시 함수 구현]

해시 충돌을 최대한 적게 발생 시키게 하기 위해 K 와 mod 값을 선택해야 하는데

두 값 모두 소수 (prime number) 로 선택하는 편이 좋다고 한다.

• K: 31, 53, 101, 127, 131, 137, ...
• mod: 1e9+7 과 같은 큰 수. (1e9+3, 1e9+9)
  # 십만자리 : 1e5+3
  # 백만자리 : 1e6+3

특히 K 는 문자열의 상황에 따라 다른데,

• 알파벳 소문자로 구성 된 경우 : 31, 127, 131, ...
• 알파벳 대소문자 + 숫자 로 구성된 경우 : 53, 131, 911, ...
• 그 외, 257, 997, 1009

최소 31 부터 소수 인 값을 선택하면 좋음

특히, 거듭제곱 등의 연산이 발생하기 때문에 overflow 에 유의하도록 한다.