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

問題描述

給定兩個字符串 A, B，求它們的最長公共子串長度。字符串長度 ≤ 100000。

後綴數組 + Height 數組

將兩字符串拼接：S = A + '#' + B（# 為不在字符集中的分隔符）。構建 S 的後綴數組 SA 和 Height 數組。Height[i] 表示 SA[i] 和 SA[i-1] 的最長公共前綴。答案為所有 Height[i] 中，對應的兩個後綴分別屬於 A 和 B 的最大值。

關鍵步驟

1. 倍增法構建後綴數組 O(n log n)。
2. 構建 Height 數組 O(n)。
3. 遍歷 i=1..n-1，若 SA[i] 和 SA[i-1] 一個 < lenA，一個 > lenA，更新答案。

代碼框架（核心部分）

struct SuffixArray {
    int s[maxn], sa[maxn], rk[maxn], ht[maxn];
    int t[maxn], t2[maxn], c[maxn];
    int n;
    void build_sa(int m) { ... } // 倍增法
    void build_height() { ... }  // 利用 rk 數組
};

int main() {
    char A[100010], B[100010];
    while (scanf("%s%s",A,B)==2) {
        SA sa;
        int lenA=strlen(A), lenB=strlen(B);
        for (int i=0;ilenA) || (p1>lenA && p2