String Searching Algorithm September 30, 2013

Rabin-Karp-Algorithm

라빈 카프 알고리즘은 해시 값을 이용한 문자열 검색 알고리즘이다. 문자열의 해시 값은 아래와 같이 나타낼 수 있다.

$H = s[0]*B^{(m-1)} + s[1]*B^{(m-2)} + s[2]*B^{(m-3)} + … + s[m-2]*B^1+s[m-1]*B^0$

그런데 이렇게 표시했을 경우 생길 수 있는 문제점이 해시 키값이 굉장히 큰 수가 될 수 있다는 단점이 있다. 따라서 이를 해결하기 위하여 나머지를 이용한다. 일반적으로

$A+B=C$ 는 $(A%M+B%M)%M = C%M$으로 나타낼 수 있고,

$AB+C$ 는 $((A%M)(B%M))%M = C%M$으로 나타낼 수 있다.

이를 위 해시값 식에 적용하면,

$H%M$ = $(((s[0]%M)(B^{(m-1)}%M))%M + ((s[1]%M)(B^{(m-2)}%M))%M + ((s[2]%M)*(B^{(m-3)}%M))%M+ … $

$+ ((s[m-2]%M)(B^1%M))%M + ((s[m-1]%M)(B^0%m))%M)%M$

으로 나타낼 수 있다.

이제 패턴의 길이를 m이라 하고, m이 3일 때를 생각해보면,

$H_0$ = $H_{s[0]…s[2]}$ = $s[0]*B^2+s[1]*B^1+s[2]*B^0$ 이고,

$H_1$ = $H_{s[1]…s[3]}$ = $s[1]*B^2+S[2]*B^1+s[3]*B^2$ 이다.

둘을 잘 정리하면

$H_1$ = $(H_0-s[0]*B^2)*B+s[3]$ 이 된다.

이를 일반화하면,

$H_i$ = $(H_{i-1}-s[i-1]*B^{(m-1)})*B+s[i+m-1]$ 이고, 모듈러 연산을 하면

$H_i%M$ = $((((H_{i-1}%M-((s[i-1]%M)(B^{m-1}%M))%M)%M)(B%M))%M+s[i+m-1]%M)%M$ 이다.

이 때, 음수가 나타날 수 있으므로,

$A-B=C$ 는 $(A%M-B%M+k*M)%M = C%M$ 룰을 적용하면 된다.

Kruth-Morris-Pratt-Algorithm

조금이따가 써야겠다.

Topcoder Algorithm Tutorial