Labin-Karp 알고리즘

반응형

Labin-Karp 알고리즘 이란?

라빈카프 알고리즘이란 이전에 계산한 T[i, i+M-1] 부분 문자열의 해시 값을 이용해서 T[i+1, i+M]의 해시값을 빠르게 구하는 알고리즘이다

 

구체적인 내용은 이전 KMP 알고리즘을 소개할 때 했으므로 넘어가겠다.

아래는 라빈카프를 활용한 문제풀이이다.

 

이 문제의 핵심은 두번 이상 등장하는 부분 문자열중 가장 길이가 긴 것을 구해야 하므로

부분 문자열의 길이가 모두 상이 하므로 이분탐색으로 임의의 K를 찾아나가며 가장 긴 길이를 구하는 방식으로 해야한다.

탐색을 하면서 가능한 모든 위치에서 길이 mid인 부분 문자열의 해시값을 구해, 해시값이 충돌했다면 같은 문자열이 앞에 등장했는지 모두 비교를 하고, 아니라면 현재 문자열의 첫 인덱스를 해시에 저장하고 계속 진행한다.

코드는 다음과 같다.

 

#BOJ 3033:가장 긴 문자열

 

#include <iostream>
#include <vector>
using namespace std;
 
const int MOD = 100003;
int mod(long long n) {
    if (n >= 0)    return n%MOD;
    return ((-n / MOD + 1)*MOD + n) % MOD;
}
vector<int> pos[MOD];    //pos[i] : 해시값이 i인 부분 문자열이 가리키는 위치들
 
int main() {
    int L;
    char str[200001];
    register int i, j;
 
    scanf("%d %s", &L, str);
    //binary search로 길이K를 찾는다.
    int s = 0, e = L;    //s : 가능, e : 불가능
    while (s + 1 < e) {
        int mid = (s + e) / 2;
        int hashret = 0, power = 1;
        for (i = 0; i < MOD; i++) {
            pos[i].clear();
        }
        bool isfound = false;
        //가능한 모든 위치에서 길이 mid인 부분 문자열의 해시값을 구해보며 처리
        for (i = 0; i <= L - mid; i++) {
            //해시값 계산
            if (i == 0) {
                for (j = 0; j < mid; j++) {
                    hashret = mod(hashret +1LL * str[mid - 1 - j] * power);
                    if (j < mid - 1)
                        power = mod(power * 2);
                }
            }
            else {
                hashret = mod(2 * (hashret - 1LL * str[i - 1] * power) + str[i + mid - 1]);
            }
            //해시값 충돌이 일어났다면 같은 문자열이 앞에 등장했는지 모두 비교
            if(!pos[hashret].empty()){
                for (int p: pos[hashret]) {    // p : 현재 부분문자열의 첫 인덱스
                    bool issame = true;
                    for (j = 0; j < mid; j++) {
                        if (str[i + j] != str[p + j]) {
                            issame = false;
                            break;
                        }
                    }
                    if (issame) {    //동일한 부분 문자열이 등장했다면
                        isfound = true;
                        break;
                    }
                }
            }    
            if (isfound)    
                break;    //찾았다
            else
                pos[hashret].push_back(i);    //찾지 못하면 해시에 현재 문자열 위치 저장하고 루프 계속
        }
        //길이 mid인 부분 문자열이 2번이상 등장했다면 s=mid,아니면 e=mid로 상하값 조정 
        (isfound ? s : e) = mid;
    }
    printf("%d\n", s);
    return 0;
}