[백준 3033] 가장 긴 문자열

문제

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

 

알고리즘

라빈 카프

 

풀이

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

길이 제한을 제외하고, 위 문제와 동일합니다. 우리는 1701번 문제를 $O(N^2)$에 해결했지만, 이 문제는 길이 제한이 20만 이므로 다른 전략을 택하도록 합시다.

 

만약 길이$m$인 문자열이 두 번 이상 등장한다고 해봅시다. 그러면 $m$보다 작은 $n$은 두 번 이상 등장함을 알 수 있을까요? 네. 이는 너무나도 확실합니다. 예를 들어 문자열 $aabaa$에서 부분 문자열 $aa$는 두번 등장함을 알 수 있고, 이보다 짧은$a$는 $aa$가 등장한 인덱스를 제외하고도 더 등장할 수가 있죠.

그렇다면 길이$m$보다 긴 길이$k$는 몇 번 등장할까요? 운이 좋다면 $m$이 등장한 만큼 등장할 수 있지만, 적어도 $m$이 등장한 횟수 이하임을 알 수 있습니다. 이러한 관찰을 통해 우리는 등장 횟수가 길이에 반비례 함을 알 수 있습니다. 즉 등장횟수가 정렬되어 있으므로 이분 탐색을 전략으로 채택할 수 있습니다.

 

남은 문제는 길이$m$이 주어졌을 때, 두 번 이상 등장함을 판단해야 합니다. KMP를 제외한 또 다른 일대일 매칭 알고리즘인 라빈 카프를 이용하여 판단하도록 합시다. 시간복잡도는 이분탐색 + 라빈카프 이므로 $O(NlogN)$ 입니다.

 

++

모듈러 2개를 사용하여, 해시값이 같다면 단순비교를 건너뛰고 같다는 판단하는 코드입니다.

$BASE$와 $MOD$를 설정할 때, $BASE$는 서로 다른 문자의 개수보다 큰 숫자를 사용하고 $MOD$는 매우 큰 소수를 사용하도록 합시다. 이 문제에선 소문자만 등장하므로 $BASE$는 26보다 큰 31을 사용했습니다.

 

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;

ll b[2], h[2];
const int MOD[2] = { 100000000 + 7,1000000000 + 9 };
const int BASE = 31;
int N;
string S;

unordered_set<ll> us;

bool ok(int m) {
    us.clear();
    rep(i, 2) b[i] = 1,h[i]=S[0];
    for (int i = 1;i < m;++i) rep(j, 2) {
        h[j] = (h[j] * BASE + S[i]) % MOD[j];
        b[j] = b[j] * BASE % MOD[j];
    }
    us.emplace(h[0] << 32 | h[1]);
    for (int i = m;i < N;++i) {
        rep(j, 2) {
            h[j] = (h[j] - S[i - m] * b[j] % MOD[j] + MOD[j]) % MOD[j];
            h[j] = (h[j] * BASE + S[i]) % MOD[j];
        }

        ll key = h[0] << 32 | h[1];
        if (us.find(key) == us.end()) us.emplace(key);
        else return true;
    }
    return false;
}

int main() {
    FAST;
    cin >> N >> S;

    int lo = 0;
    int hi = N;
    int best;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (ok(mid)) {
            best = mid;
            lo = mid + 1;
        }
        else hi = mid - 1;
    }
    cout << best;

    return 0;
}