Rabin-Karp String Matching Algorithm, 라빈-카프 알고리즘

https://www.youtube.com/watch?v=qQ8vS2btsxI 

이 영상을 참고했다!

라빈-카프 알고리즘은 String을 비교하여 긴 문자열에 짧은 문자열이 포함되어 있는지 확인하는 알고리즘이다.
brute force 방법으로, 문자열을 한칸씩 이동하며 모두 비교하는 방법부터 보이어-무어, KMP등 여러가지 방법을 공부했다.

 

라빈-카프의 핵심은, Hash function이다.

각 문자열의 값을 이렇게 할당한다고 했을 때, 'AAA' 의 값을 1 + 1 + 1 = 3으로 정의한다.

이렇게 해당 문자열의 값을 return해주는 함수가 hash 함수이다. (예시는 단순한 해시함수이다!)
'AAAAAAB' 안에 'AAB'가 존재하는지 확인하기 위해서,

'AAB'를 hash 함수에 넣고, 4라는 값을 얻었다.
'AAAAAAB' 안에 길이 3의 string중 해시가 4인것을 찾아 비교하면 되는데,'AAA' = 3이니 한칸 씩 오른쪽으로 이동하며, 'AAB'를 발견하고, string을 비교하여 찾을 수 있다!
그러나 만약 'AAEAAEACCA' 에서 'CCA' = 7 을 찾고자 할 때, 'AAE'의 hash 값도 7이기 때문에, 계속해서 문자열을 비교해줘야 한다. 이런 최악의 경우, 결국 brute Force와 다름 없이 문자열을 매번 비교해줘야 한다.
이렇게 hash 값이 동일한 경우를 spurious Hits 라고 하는데, 이 hits가 적게 일어나야 우리가 원하는 알고리즘이 된다.

때문에 hash함수를 단순하게 짜지 않고, 예를 들면 'ABC'의 경우 1 + 2 + 3이 아닌
1 * 100 + 2 * 10 + 3 * 1 = 123 으로 한다. (여기선 10개의 수만 있으므로, 실제 알파벳으로 한다면 26 + a 로 하면 된다!)
이렇게 hash 값을 지정하면, 다른 문자열은 모두 각기 다른 값을 가지게 되어 Hits가 발생할 일이 줄어든다.
긴 문자열의 길이가 M, 짧은 문자열이 N이면
시간복잡도는 최소 O(M -N + 1), 최대O(MN)이다.

Hits를 최소화 해야 시간복잡도가 개선된다.

 

 

음... 설명이 너무 부실한데 추후에 다시 업데이트하자!!