Credit
라빈-카프 알고리즘은 KMP (Knuth-Morris-Prett), Aho-Corasick과 같은 문자열 매칭 알고리즘 중 하나로, 라빈-카프 해싱을 이용하여 문자열을 O(N)에 찾는 알고리즘이다. Ref
여기서 라빈-카프 알고리즘을 안 쓰는 이유는, 라빈-카프 알고리즘에 사용되는 라빈-카프 해싱을 충돌시키는 데이터 $a$, $b$ 쌍을 아주 효율적으로 만들 수 있기 때문이다. 따라서 이 해싱, 혹은 알고리즘을 실제에서 사용한다면 큰 화를 입을 수 있다.
라빈-카프 해싱은 다음과 같이 계산된다.
Rabin-Karp Hash
소수 $p$, 데이터 $d$ (일반적으로 문자열) 에 대해, $n$은 $|d|$ 이다. ($|x|$는 $x$의 길이를 말한다.) 이때, Rabin-Karp 해시 $H(p, d)$는 다음과 같이 계산된다.
$$ H(p, d) = \sum_{i=1}^Nd[i]p^i $$
Rabin-Karp 해시의 서로 다른 데이터 $d_a$, $d_b$가 해시가 충돌한다는 것은 다음과 같이 표현된다.
$$ H(p, d_a) = H(p, d_b) \\ H(p, d_a) - H(p, d_b) = 0 \\ \sum_{i=1}^Nd_a[i]p^i -\sum_{i=1}^Nd_b[i]p^i = 0 \\ \sum_{i=1}^N(d_a[i] - d_b[i])p^i = 0 $$