[알고리즘 5분안에 마스터 하기] 라빈 카프(Rabin-Karp) 편

5분안에 마스터 하는것이기 때문에 아주 간결하고 핵심 요약만 말할것이다.

준비물 : hash에 대한 기본 지식, 이분탐색에 대한 기본 지식

 

1. 이분탐색을 돌린다.

길이가 i인 문자열이 반복으로 나온다면 그 아래는 볼 필요가 없다. 즉 이분탐색이 가능하다.

 

2. hash테이블을 이용하여 같은 문자열이 있는지 검사한다.

hash테이블을 써서 길이 i인 것들중 같은것이 있는지 체크해준다. (hash에 대한 기본지식은 알고 있기 바란다.)

시간 복잡도는 O(NlogN) 이다

 

아래의 코드는 3033 번 문제이다.

바로 코드를 보겠다.

 

#include <bits/stdc++.h>
using namespace std;
const int mod = 100003;

int f(long long x) { // x % mod 를 양수로 만들어주는 함수다.
    if(x >= 0) return x % mod;
    else return ((-x/mod+1)*mod+x) % mod;
}

int main() {
    int n;
    char a[200005];
    scanf("%d",&n);
    scanf("%s",&a);
    int lo = 0,hi = n;
    while(lo+1 < hi) {
        int h = 0,po = 1;
        int mid = (lo + hi) >> 1;
        vector <int> Hash[mod]; // hash배열 만들기
        bool found = false;
        for(int i = 0;i <= n-mid;i++) {
            if(i == 0) { // 처음이라면
                for(int j = 0;j < mid;j++) {
                    h = f(h+1LL*a[mid-j-1]*po);
                    if(j < mid-1) po = f(po*2); // 초기의 문자열로 hash값 만들기
                }
            }
            else h = f(2*(h-1LL*a[i-1]*po)+a[i+mid-1]); // 길이가 mid 이고 i번째에서 끝나는 문자열의 해시 값

            if(!Hash[h].empty()) { // hash값이 같은 것들은 직접 비교해 본다. (몇개 안한다)
                for(int p : Hash[h]) {
                    bool same = true;
                    for(int j = 0;j < mid;j++){
                        if(a[i+j] != a[p+j]) { // 다르면 그냥 break
                            same = false;
                            break;
                        }
                    }
                    if(same) {
                        found = true;
                        break;
                    }
                }
            }
            if(found) break;
            Hash[h].push_back(i); // hash테이블에 해시 값 h을 넣기
        }
        if(found) lo = mid; // 찾았으면 더 높은 길이 탐색
        else hi = mid; // 없으면 더 낮은 길이 탐색
    }
    printf("%d",lo);
}