[백준 9249] 최장 공통 부분 문자열

문제

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

알고리즘

Suffix array

풀이

LCS문제입니다. 주어진 두 문자열$A, B$를 합친 후 LCP를 구하게 되면 답을 얻을 수 있습니다.

이때 주의해야 할 점이 있습니다. 인접한 LCP를 검사할 때, 하나의 Suffix는 $A$의 일부를 포함해야 하지만, 나머지 Suffix는 $A$를 포함해선 안된다는 점입니다. 이점을 유의하지 않으면 $A$ 또는 $B$ 내에서만 LCP를 뽑아버리므로 두 문자열의 공통부분 문자열을 얻지 못하게 됩니다. 시간 복잡도는 Suffix Array와 LCP를 구해야 하므로 $O(NlogN+N)$입니다.

코드

#include <bits/stdc++.h>
#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;

string A, B, C;
int al, bl, idx, ans;
vector<int> g, ng, ordered, lcp, cnt, sfx;

void getsfx(string& s) {
    int p = 1;
    int n = s.size();
    int mx = max(257, n + 1);

    g.resize(n + 1); ng.resize(n + 1);
    sfx.resize(n); ordered.resize(n);

    for (int i = 0;i < n;++i) g[i] = s[i];

    for (int t = 1;t < n;t <<= 1) {
        cnt.clear(); cnt.resize(mx);
        for (int i = 0;i < n;++i) ++cnt[g[min(i + t, n)]];
        for (int i = 1;i < mx;++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1;i >= 0;--i) ordered[--cnt[g[min(i + t, n)]]] = i;

        cnt.clear(); cnt.resize(mx);
        for (int i = 0;i < n;++i) ++cnt[g[i]];
        for (int i = 1;i < mx;++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1;i >= 0;--i) sfx[--cnt[g[ordered[i]]]] = ordered[i];

        if (p == n) break;
        p = 1;

        auto cmp = [&](int i, int j) {
            if (g[i] == g[j]) return g[i + t] < g[j + t];
            return g[i] < g[j];
        };

        ng[sfx[0]] = 1;

        for (int i = 1;i < n;++i) {
            if (cmp(sfx[i - 1], sfx[i])) ++p,ng[sfx[i]] = ng[sfx[i - 1]] + 1;
            else ng[sfx[i]] = ng[sfx[i - 1]];
        }
        g = ng;
    }

    lcp.resize(n);
    for (int i = 0;i < n;++i) g[sfx[i]] = i;
    for (int i = 0, k = 0;i < n;++i, k = max(k - 1, 0)) {
        if (g[i] == n - 1) continue;
        for (int j = sfx[g[i] + 1];s[i + k] == s[j + k];++k);
        lcp[g[i]] = k;
    }

    for (int i = 0;i < n - 1;++i) {
        if (sfx[i] < al && al < sfx[i + 1]||sfx[i+1]<al&&al<sfx[i]) {
            if (lcp[i] <= al) {
                if (ans < lcp[i]) {
                    ans = lcp[i];
                    idx = sfx[i];
                }
            }

        }
    }
}

int main() {
    FAST;
    cin >> A >> B;
    al = A.size();
    bl = B.size();
    C = A + '$' + B;
    getsfx(C);
    cout << ans<<'\n';
    cout << C.substr(idx, ans);
    return 0;
}