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