백준저지 1605번 반복 부분문자열 문제 풀이

https://www.acmicpc.net/problem/1605

1605번: 반복 부분문자열

백준 1605번 문제 - 반복 부분 문자열 입니다.

 

Brute-force로 풀 시에는

모든 부분 문자열을 다 알아내면 O(N^2)이 나올 것이고, 각각을 다 비교하려면 O(N)이 걸리므로

 

총 O(N^3)이 되는데, N=20만이므로, 이 방법으로는 풀 수 없습니다.

 

대충 O(NlogN) 정도 이하의 방법이 필요합니다.

 

여기서 사용할 방법은 바이너리 서치 + 롤링 해시 입니다.

 

원래 문제는 여기서 나타나는 가장 긴 반복 부분 문자열의 길이를 구하는것인데요, 이를

다음 문제로 바꾸어서 봅시다.

 

T(L) => 길이 L인 반복 부분문자열이 존재하는지 아닌지를 확인하는 문제.

 

만약 길이 L인 반복 부분 문자열이 존재한다면 L-1 길이의 반복 부분 문자열도 존재할 것입니다.

간단한 예로 abcdefg 라는 문자열이 두번 나왔고, 이 길이가 7이면

abcdef라는 문자열도 2번 이상 나왔을 것이며, 이 길이는 6입니다.

 

이러한 성질을 이용하면 바이너리 서치를 할 수 있습니다. 즉 T(L)라는 문제를 logL번만 풀면 T(L) == True를 만족하는 최대 L을 구할 수 있지요.

 

반복 부분 문자열의 길이는 최대 L-1이 될 것이고, 최소 0이 될 것입니다.

원문이 a가 10개짜리인 문자열이라면, a가 9개 나온 부분 문자열이 2번 나온것이기 때문이죠.

 

이제 T(L)을 빠른 시간안에 푸는 방법을 생각해봅시다.

 

이는 롤링해시를 이용해서 풀 수 있습니다.

 

문자열 S의 길이가 L이고, 각각의 i번째 문자가 S[i]라고 할 때, 해당 문자열은 다음과 같은 방식으로 해시를 할 수 있습니다.

 

적당한 상수 p 값을 잡고

 

hash(S) = S[1] * p^(L-1) + S[2] * p^(L-2) + ... + S[L-1] * p^1 + S[L] * p^0

 

이때 각각의 S[i]는 영어 소문자이므로 26가지 글자를 가질 수 있으므로, p는 26보다는 큰 적당한 소수를 잡는게 좋겟죠.

저는 29를 사용했습니다.

 

그리고 이 hash 값을 적당한 소수 (저는 10007를 사용했습니다) 로 MOD 연산하여 hash table에 집어 넣습니다.

 

해당 문자열이 나타나는 첫번째 index를 넣어놓고, hash값이 같을 경우, 실제로 같은지 체크를 하는 식으로 롤링 해시를 구성해 보았습니다.

 

매번 저런식으로 hash값을 구하면 시간이 많이 걸리므로, 첫번째만 L만큼의 선형으로 구하고, 두번째 부터는 슬라이딩 윈도우 테크닉을 이용해서 추가되는 글자에 해시값만 추가하고, 떨어져나가는 글자의 해시값만 빼주는 식으로 O(1)로 구해버립니다.

 

아마 요런방식이 문자열 비교 알고리즘인 라빈-카프 알고리즘과 비슷할 것입니다. (저도 그렇다고만 들었고, 아직 라빈-카프 알고리즘을 공부하지 않아서 정확하겐 모르는 상태입니다.)

 

이런식으로 구성하면 해시 충돌이 많이 일어나지 않는다면 대충 O(L)만에 중복되는 문자열이 있는지를 확인할 수 있습니다. 즉 T(L)문제를 풀 수 있죠.

 

다른 사람들 코드를 보니, 이 방식 말고도 풀 수 있는 방법이 더 많은 것으로 보입니다. LCP(Longest Common Prefix) 라던지 등등 문자열과 관련된 다양한 테크닉들을 활용하더군요.

 

일단 제가 풀이한 코드를 첨부하겠습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
char str[200005];
const int p = 29;
const int MOD = 10007;
int Len;
int pexp[200005];

vector<int> hashTable[10007]; //시작 index를 갖는다.
void init();
bool real_match(int s1, int s2, int L) {
    for (int i = 0; i < L; i++) {
        if (str[s1 + i] != str[s2 + i]) {
            return false;
        }
    }    
    return true;
}
bool ok(int L) {
    init();
    //길이 L의 중복 부분문자열이 존재하는지를 리턴
    int hash = 0;
    for (int i = 0; i < L; i++) {
        hash *= p;
        hash += str[i] - 'a';
        hash %= MOD;
    }
    hashTable[hash].push_back(0);
    for (int i = L; i < Len; i++) {
        hash -= (str[i - L] - 'a') * pexp[L - 1] % MOD;
        hash = (hash + MOD) % MOD;
        hash *= p;
        hash += str[i] - 'a';
        hash %= MOD;
        if (hashTable[hash].size()) {
            for (int idx : hashTable[hash]) {
                if (real_match(idx, i - L + 1, L))
                    return true;
            }
        }
        hashTable[hash].push_back(i-L+1);
    }
    return false;
}
void solve() {
    scanf("%s", str);
    int l = 0, r = Len;
    while (l < r) {
        int m = (l + r + 1) / 2;
        if (ok(m)) l = m;
        else r = m - 1;
    }
    cout << l << endl;
}
void pre() {
    pexp[0] = 1;
    for (int i = 1; i <= 200000; i++) {
        pexp[i] = pexp[i - 1] * p % MOD;
    }
}
int main() {
    pre();
    cin >> Len;
    solve();
} 

void init() {
    for (int i = 0; i < MOD; i++) {
        hashTable[i].clear();
    }
}