라빈 카프 알고리즘(Rabin-Karp Algorithm)

1. 개념

해싱을 사용해 일대일 매칭을 하는 알고리즘이다.

어떠한 S에서 W를 찾을때 S의 길이를 N, W의 길이를 M으로 가정하자.

제일 무식한 방법으로 W를 찾을 때에는 O(N*M)의 시간복잡도를 가지고 찾아야한다. (KMP 글 참고)

라빈 카프 알고리즘은 문자열을 모든 위치에서 비교해보는데,

먼저 해당 위치의 해시값을 비교하고 같다면 그 후에 단순 비교를 시작한다.

해당 위치의 부분 문자열과 찾으려는 단어가 다르면서 해시값이 같을 수는 있지만,

같은데 해시값이 다른 경우는 불가능한 점을 이용한 것이다.

 여기서 중요한 점은 문자열을 해싱하려면 적어도 문자열 길이만큼 O(M)의 소요시간이 들어간다.

매번 해시값을 계산하다보면 시간 복잡도가 O(N*M)이 되어서 알고리즘이 쓸모가 없어진다.

그렇기 때문에 해시값을 더 빨리 계산하기 위해 Rabin fingerprint 해시 함수를 사용한다.

2. 구현

Rabin fingerprint

 여기서 m의 값은 각 자리 문자의 아스키코드를 넣는다. x의 값은 아무거나 상관없다, (보통 2를 넣음)

 이런 식으로 함수를 사용하면 H(x)를 계산하는 과정은 O(M)이 맞지만, S의 관점에서 보면 만약 S[i:i+M-1]의 해시값을 알고 있다면,

S[i+1:i+M], 즉, 바로 다음 위치의 해시값을 바로 구할 수 있다.

 이렇게 식을 수정하면 H(S[i+1:i+M])은 바로 이전 위치 해시값 H(S[i:i+M-1])을 알면 O(1)에 계산할 수 있는 구조를 띄운다.

** 출처 : https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220927272165&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F