[백준] 가장 긴 문자열 + 라빈 카프 알고리즘

문제

상근이는 꿈에서 길이가 L인 문자열을 외웠다.

꿈에서 깬 상근이는 이 문자열을 종이에 적었다. 종이를 적던 중에 어떤 문자열은 두 번 이상 등장하는 것 같은 느낌을 받았다.

문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것을 찾는 프로그램을 작성하시오. (부분문자열은 겹쳐서 등장할 수도 있다)

입력

첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다.

출력

첫째 줄에 두 번 이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이를 출력한다. 만약 그러한 문자열이 없을 때는 0을 출력한다.

라빈 카프 알고리즘

문자열S에 부분문자열 T가 존재하는지 확인하는 문제입니다.

KMP알고리즘과 같은 목적으로 사용하는 알고리즘이지만,

사용방식은 완전히 다릅니다.

 

라빈 카프알고리즘은 해싱(Hashing)을 사용합니다.

문자열 S를 해쉬함수를이용해 해싱 테이블에 입력합니다.

 

예를들어 "ABCDE"라는 문자열 S가 있을때, 해쉬함수 H(x)=x%10이라 할때 

해쉬값 H(S) 를 인덱스로 하는 테이블에 저장이 됩니다.

 

문자열 T가 "BC"라고 할때, 문자열 S의 처음부터 길이 2로 끊어서 해시값 H(T)와 비교합니다.

1. "AB" >> H(AB)

2. "BC" >> H(BC) >>동일!

3. "CD" >> H(CD)

4. "DE" >> H(DE)

 

이런식으로 비교해가면서 존재하는지 확인할텐데, 해쉬값 H(x)이 동일해 충돌(Collide)할 수 있습니다.

따라서 해쉬 테이블은 연결리스트나, 배열로 저장해야합니다.

 

따라서 이때 사용하는 해시함수 H(x)는  Rabin fingerprint를 사용합니다.

 

그리고 보통 x=2를 사용합니다.

 

이렇게 사용하면,, 한번의 해쉬값 비교 이후 다음 해쉬값을 계산할때, 맨 앞의 값만을 빼고 맨 뒤값을 새로 넣는것만으로도 새로운 해쉬값을 계산할 수 있습니다.

 

 

이를 이용해 3033 가장 긴 문자열 문제를 풀어보겠습니다.

 

길이가 L인 문자열에서 가장 긴 반복되는 문자열의 길이를 알아내야합니다.

만약 그 길이가 K일때, K-1일때도 K-2일때도 1일때도 반복되는 문자열이 성립합니다.

따라서 이분탐색을 사용합니다.

 

문자열 S="abcabc"라고 가정할때 mid(찾고자하는 반복되는 문자열의 길이) = 3이라고 합시다. (le=0 ri=6 mid=(0+6)/2)

처음부터 문자 3개씩 살펴봅니다.

1) 'abc'

2) 'bca'

3) 'cab'

4) 'abc'

이렇게 확인하면서 Mod[H(x)]에 존재하는지 확인하고, 넣습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e5 + 3;

int MOD(ll n) {
    if (n >= 0) return n % mod;
    else return ((-n / mod + 1) * mod + n) % mod;
}

int main() {
    int L;
    char s[200002];
    scanf("%d %s", &L, s);
    int le = 0, ri = L, mid, ans = 0;
    while (le <= ri) { //이분탐색
        mid = (le + ri) / 2;
        ll power = 1;
        int H = 0;
        vector<int> pos[mod];
        bool found = false;

        for (int i = 0; i <= L - mid; i++) {
            if (i == 0) { //i=0일때 초기화
                for (int j = 0; j < mid; j++) {
                    H = MOD(H + s[mid - 1 - j] * power);
                    if (j < mid - 1)power = MOD(power * 2);
                }
            }
            else {
                //앞을 지우고 뒤를 넣습니다.
                H = MOD(2 * (H - s[i - 1] * power) + s[i + mid - 1]);

            }

            //만약 해쉬값으로 된 인덱스에 존재한다면
            if (!pos[H].empty()) {
                for (auto r : pos[H]) {
                    bool flag = true;
                    for (int j = 0; j < mid; j++) {
                        if (s[i + j] != s[r + j]) {
                            flag = false;
                            break;
                        }
                    }

                    if (flag) {
                        found = true;
                        break;
                    }
                }
            }
            //발견
            if (found) break;

            //발견하지 못했으면 해쉬에 집어넣습니다.
            else pos[H].push_back(i);
        }
        if (found) {
            le = mid + 1;
            ans = mid;
        }
        else ri = mid - 1;
    }
    cout << ans;
}