3033번: DVAPUT

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

Rabin-Karp 알고리즘으로 $O(l)$에 길이가 x인 같은 문자열이 두 번 나오는지 확인할 수 있다.
x에 대해 파라메트릭 서치를 한다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
const long long mod = (1LL << 55) - 55;
int l;
char s[200001];
int main() {
    scanf("%d%s", &l, s);
    int low = 1, up = l, mid;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_set<long long> st;
        long long p = mod - 1, t = 0;
        int i = 0;
        for (; i < mid; i++) t = (t * 127 + s[i]) % mod, p = p * 127 % mod;
        for (; i <= l; i++) {
            if (st.find(t) != st.end()) break;
            st.insert(t);
            t = (t * 127 + p*s[i - mid] + s[i]) % mod;
        }
        i > l ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", up);
    return 0;
}

답은 lcp 길이의 최댓값이다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<algorithm>
using namespace std;
int l, c[200000], a[200000], b[200000], sa[200000], sz, r;
char s[200001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < l; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = l; i--;) sa[--c[a[b[i]]]] = b[i];
}
int main() {
    scanf("%d%s", &l, s);
    sz = max(l, 128);
    for (int i = 0; i < l; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= l; i <<= 1) {
        k = 0;
        for (int j = l - i; j < l; j++) b[k++] = j;
        for (int j = 0; j < l; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < l; j++) b[sa[j]] = !j || sa[j - 1] + i < l && sa[j] + i < l && a[sa[j - 1]] == a[sa[j]] && a[sa[j - 1] + i] == a[sa[j] + i] ? k : ++k;
        for (int j = 0; j < l; j++) a[j] = b[j];
    }
    for (int i = 0, j = 0; i < l; r = max(r, j ? j-- : 0), i++)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
    printf("%d", r);
    return 0;
}