9249번: 최장 공통 부분 문자열

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

길이가 x인 공통 부분 문자열이 존재하는지 Rabin-Karp 알고리즘으로 확인 가능하다.
x에 대해 파라메트릭 서치를 한다.

$O(l\lg l)$

#include<cstdio>
#include<cstring>
#include<unordered_map>
using namespace std;
const long long mod = (1LL << 55) - 55;
char a[200001], b[200001];
int main() {
    scanf("%s%s", a, b);
    int low = 1, up = 2e5, mid, r = 2e5;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_map<long long, int> mp;
        long long u = 0, v = 0, p = mod - 1;
        int i = 0;
        for (; i < mid; i++) p = p * 127 % mod, u = (u * 127 + a[i]) % mod, v = (v * 127 + b[i]) % mod;
        for (; a[i - 1]; i++) mp[u] = i, u = (u * 127 + a[i] + a[i - mid] * p) % mod;
        for (i = mid; b[i - 1]; i++) {
            if (mp.find(v) != mp.end()) { r = i; break; }
            v = (v * 127 + b[i] + b[i - mid] * p) % mod;
        }
        b[i - 1] ? low = mid + 1 : up = mid - 1;
    }
    b[r] = 0;
    printf("%d\n%s", up, b + r - up);
    return 0;
}

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;
}