SPOJ 1811 LCS：後綴自動機求最長公共子串

問題

給定兩字符串 S, T（長度 ≤ 10⁵），求最長公共子串長度。

後綴自動機 (SAM) 核心

• 狀態：len（最長長度）、link（後綴鏈接）、next[26]（轉移）。
• 擴展字符 c：創建新狀態 cur，沿 link 回溯補轉移，必要時克隆分裂。

匹配過程

在 SAM 上跑字符串 T：
維護當前狀態 p 和匹配長度 l。
若有轉移 c → p=next[p][c], l++。
否則沿 link 回溯直到有轉移或到根，更新 l = len[p]+1。
記錄最大 l 即答案。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
struct SAM {
    struct State { int link, len, next[26]; } st[MAXN];
    int sz, last;
    SAM() { init(); }
    void init() { sz = last = 0; st[0].link = -1; st[0].len = 0; memset(st[0].next, 0, sizeof(st[0].next)); }
    void extend(int c) {
        int cur = ++sz; st[cur].len = st[last].len + 1; memset(st[cur].next, 0, sizeof(st[cur].next));
        int p = last;
        while (p != -1 && !st[p].next[c]) { st[p].next[c] = cur; p = st[p].link; }
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;
            else {
                int clone = ++sz; st[clone] = st[q]; st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    int lcs(const string &t) {
        int p = 0, l = 0, best = 0;
        for (char ch : t) {
            int c = ch - 'a';
            if (st[p].next[c]) { p = st[p].next[c]; ++l; }
            else {
                while (p != -1 && !st[p].next[c]) p = st[p].link;
                if (p == -1) { p = 0; l = 0; }
                else { l = st[p].len + 1; p = st[p].next[c]; }
            }
            best = max(best, l);
        }
        return best;
    }
};
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s, t;
    while (cin >> s >> t) {
        SAM sam;
        for (char ch : s) sam.extend(ch - 'a');
        cout << sam.lcs(t) << '\n';
    }
    return 0;
}

複雜度

構建 SAM O(|S|)，匹配 O(|T|)，總線性，空間 O(|S|)。