[Algorithm] Rabin - Karp

mississippi라는 문자열이 있다. 여기에서 ssi라는 문자열을 찾으려고 한다면 어떻게 해야 할까?

완전 탐색을 사용한다면 O(NM)의 시간 복잡도 안에서 해결할 수 있을거라고 생각한다.

앞글자가 일치하는 단어를 찾고 그 이후부터 글자가 동일한지 아닌지를 비교하면 될것이다.

하지만 이런 방법은 당연히 시간초과가 날 수 밖에 없다. 

하지만 Rabin-Karp알고리즘을 사용하면 그 문제를 해결 할 수 있다.

 

Rabin - Karp 알고리즘은 문자열 검색을 할 때 해시값을 이용하는 기법이다.

패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시값과 비교할 문자열의 부분 문자열의 해시값만을 비교한다.

최악의 경우에 O(NM)의 시간복잡도를 가지지만, 평균적으로는 선형시간의 시간 복잡도를 가지기 때문에 효율적이라고 할 수 있다.

라빈카프 알고리즘이 해시 값을 이용한다고 했는데 라빈 카프알고리즘에서 사용되는 해시 함수는 Rabin Fingerprint라고 부르고 아래와 같은 형태를 가진다.

 

 

문자열의 각각의 단어를 문자로 인식한게 아니라 앞서 Hashing에 관한 글을 포스팅했을 때 처럼 숫자로 보고 그 값을 10진수로 부꾸는 과정임을 알 수 있다.

 

앞서 언급한 mississippi라는 문자열에서 ssi를 잧으려면 어떻게 해야 할까?

우선 찾으려는 문자열을 해싱하고, 찾는 문자열의 길이만큼 비교하는 문자열을 해싱한다.

그 다음에 비교하는 문자열에서 한글자씩 이동하면서 전체의 해쉬값을 구하는 것이 아니라. 세로 추가되는 문자와 그 전에 읽었던 해쉬 값을 이용해서 그 다음 부분 문자열의 해쉬값을 구하면 된다. 

예를 들어서 처음에 mis라는 단어로 해쉬값을 만들었다면 그 다음 단어를 고려할 때 전체를 다시 계산하는 것이 아니라 m에 해당하는 해쉬값을 빼주고 다른 단어들의 단위를 한자리 올린 후에 s에 해당하는 해쉬값을 더해 줌으로서 iss라는 해쉬 값을 찾을 수 있다고 할 수 있다.

이 과정을 그림으로 나타내면 아래와 같다.

 

 

그림을 보면 mississippi의 부분 문자열 9개중에 2번째와 5번째의 해쉬 값이 5894로 T의 해쉬값과 동일함을 알 수 있다.

매번 부분 문자열의 해쉬값을 구해준다면 Brute Force한 방법과 동일한 방법이 되지만 그림에서 보이듯이 이전의 해쉬 값을 이용한다면 O(N)의 시간복잡도만에 부분 문자열을 모두 비교할 수 있다. 

 

이를 좀더 활용한 문제는 BOJ의 찾기(https://www.acmicpc.net/problem/1786)이라는 문제인데 문제에 나타나는 설명은 사실 KMP알고리즘이지만, 라빈 카프를 통해서도 풀 수 있기때문에 설명은 라빈 카프를 이용해서 하려고 한다.

 

이 문제의 풀이는 다음과 같다.

1. P를 해싱하고 P의 길이만큼 S도 앞에서부터 해싱한다.

1. 라빈 카프 알고리즘을 통해서 앞에서부터 P의 길이 만큼씩 해쉬 값을 확인하면서 같다면 그 위치를 배열에 집어넣는다.

1.  S의 탐색이 끝나면 T와 같았던 부분 문자열의 개수를 출력하고, 그 위치들을 차례로 출력한다.  

>#include <iostream>
#include <string>
using namespace std;
 
const long long base = 256;
const long long MOD = 1e9 + 9;
string t, p;
long long tlen, plen;
int res[1000001];
int rind;
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    getline(cin, t);
    getline(cin, p);
    tlen = t.length(); plen = p.length();
 
    long long pattern = 0, str = 0, power = 1;
    for(int i = 0; i < plen; i++){
        pattern = (pattern * base) % MOD;
        pattern = (pattern + p[i]) % MOD;
        str = (str * base) % MOD;
        str = (str + t[i]) % MOD;
        if(i < plen - 1) power = (power * base) % MOD;
    }
 
    rind = 0;
    for(int i = 0; i <= tlen - plen; i++){
        if(pattern == str) res[rind++] = i + 1;
        str = (((str - (t[i] * power) % MOD + MOD) % MOD * base) % MOD + t[i + plen]) % MOD;
    }
    cout << rind << "\n";
    for(int i = 0; i < rind; i++)
        cout << res[i] << " ";
    return 0;
}