POJ 2774 Long Long Message：後綴數組求兩字符串最長公共子串

問題轉化

給定兩個長字符串（各 ≤ 100,000），中間可能夾雜干擾字符。兩字符串源自同一原始短信，兩側各有冗餘。求原始短信最大可能長度 → **兩字符串的最長公共子串長度**。

後綴數組解法

1. 將兩字符串用一個**不在字符集中的分隔符**（如 ASCII 127）連接：S = s1 + char(127) + s2。
2. 構建 S 的後綴數組 SA 及高度數組 Height（Height[i] = LCP(SA[i], SA[i-1])）。
3. 遍歷 Height，若 SA[i] 和 SA[i-1] 分屬兩個原字符串（一個 < 分隔符位置，一個 > 分隔符位置），則 Height[i] 為公共子串長度候選，取最大值。

關鍵代碼（DC3/SA-IS 或倍增算法均可，此處用倍增）

#include 
using namespace std;

const int MAXN = 200200;
int sa[MAXN], rk[MAXN], tmp[MAXN], h[MAXN], c[MAXN];
char str[MAXN];

bool cmp(int* r, int a, int b, int l, int n) {
    return r[a] == r[b] && a+l < n && b+l < n && r[a+l] == r[b+l];
}

void radix_sort(int n, int m) {
    fill(c, c+m, 0);
    for (int i = 0; i < n; ++i) c[rk[i]]++;
    for (int i = 1; i < m; ++i) c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i) sa[--c[rk[tmp[i]]]] = tmp[i];
}

void build_sa(int n, int m = 128) {
    for (int i = 0; i < n; ++i) rk[i] = str[i], tmp[i] = i;
    radix_sort(n, m);
    for (int len = 1; len < n; len <<= 1) {
        int p = 0;
        for (int i = n-len; i < n; ++i) tmp[p++] = i;
        for (int i = 0; i < n; ++i) if (sa[i] >= len) tmp[p++] = sa[i] - len;
        radix_sort(n, m);
        swap(rk, tmp);
        rk[sa[0]] = p = 0;
        for (int i = 1; i < n; ++i)
            rk[sa[i]] = cmp(tmp, sa[i], sa[i-1], len, n) ? p : ++p;
        m = p + 1;
        if (m >= n) break;
    }
}

void build_height(int n) {
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (rk[i] == 0) { h[0] = 0; continue; }
        int j = sa[rk[i]-1];
        while (i+k < n && j+k < n && str[i+k] == str[j+k]) ++k;
        h[rk[i]] = k;
        if (k) --k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> str) {
        int len1 = strlen(str);
        str[len1] = 127; // 分隔符
        cin >> str + len1 + 1;
        int n = strlen(str);
        build_sa(n);
        build_height(n);
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            int a = sa[i], b = sa[i-1];
            if (a > b) swap(a, b);
            if (a < len1 && b > len1) // 跨兩字符串
                ans = max(ans, h[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 構建 SA：O(n log n)，n ≤ 200,000 完全足夠。
• 構建 Height：O(n)。
• 總時間 < 1s，空間 < 10MB。

注意事項

• 分隔符必須**小於所有字符**（此處用 127，字符為 'a'-'z'），保證後綴排序正確分隔。
• 輸入可能多組測試，直到 EOF。
• 若用 DC3/SA-IS 可達 O(n)，但倍增法常數小、代碼短，工程上常用。