POJ 3415 後綴自動機 (SAM) 求長度 ≥ k 的公共子串數量

問題描述

給定兩個字符串 A、B（大寫字母，長度 ≤ 100,000）。求兩字符串所有公共子串中，長度 ≥ k 的子串對數（位置不同算不同子串）。

核心思路：SAM + 狀態計數

1. 對 A 構建 SAM。每個狀態存 len（最長長度）、link（父鏈接）、next[26]。
2. 對 B 在 SAM 上匹配，記錄每個狀態被匹配到的次數 right（即 B 中有多少不同位置的子串對應該狀態）。
3. 匹配過程中，維護當前匹配長度 lcs。當 lcs ≥ k 時，當前狀態貢獻的合法子串數為 lcs - max(k, link.len+1) + 1（不固定），直接累加到答案，並將父狀態的 sum++（表示父狀態被匹配到一次）。
4. 匹結束後，按 len 遞減拓撲序傳播 sum（子狀態 sum 加到父狀態）。
5. 遍歷所有狀態，對 len ≥ k 的狀態，其固定貢獻為 sum * right * (len - max(k, link.len+1) + 1)，累加到答案。

關鍵細節

• SAM 狀態數 ≤ 2×|A|。
• right 計算：匹配時每走一步，當前狀態 right++；最後拓撲序傳播到父鏈接。
• sum 計算：匹配時動態處理不固定部分，固定部分留到最後用 sum 乘 right。
• 父狀態 link.len 即該狀態最短長度 - 1。

代碼框架

struct SAM {
    struct Node {
        int len, link, next[26];
        long long right, sum;
        Node(int l=0): len(l), link(-1), right(0), sum(0) { memset(next, -1, sizeof(next)); }
    };
    vector st;
    int last;
    SAM(int maxlen=0) { st.reserve(2*maxlen); st.emplace_back(0); last=0; }
    void extend(char ch) { ... }  // 標準 SAM 擴展
    void count_right(const string& s) { ... }  // 匹配 B，計算 right
    void topo_sum() { ... }  // 拓撲序傳播 sum
    long long query(int k) { ... }  // 計算答案
};

複雜度

構建 SAM O(|A|)，匹配 O(|B|)，拓撲序 O(|SAM|)，查詢 O(|SAM|)。總時間 O(|A|+|B|)，空間 O(|A|)。完美應對 10 萬級數據。

SAM 模板價值

本題展示了 SAM 解決「多字符串公共子串統計」的強大能力，是進階字符串算法必刷題。