HDU 3518 Boring Counting：後綴數組 + 枚舉長度統計子串出現次數

題目大意

給字符串 s (長 n ≤ 1000)，求有多少**不同的非空子串**在 s 中**至少出現兩次**（不重疊？題目為「至少兩次」，允許重疊）。輸出滿足條件的不同子串數量。多測試案例。

解法：後綴數組 + Height 數組 + 枚舉長度

• 構建後綴數組 `sa` 和 `height` 數組（相鄰後綴 LCP）。
• 對於固定長度 `L`，連續的後綴若 `height ≥ L`，則它們共享長度 ≥ L 的前綴，即某長度為 L 的子串出現了多次。
• 掃描 `height`，將連續 `height ≥ L` 的段分組，每組對應一個至少出現兩次的長度-L 子串。但需去重：同一子串可能在多個組中出現？不，後綴數組性質保證每個不同子串對應唯一的連續區間。故直接計算滿足 `height ≥ L` 的連續區間數即為長度 L 的合法子串數。
• 枚舉 L = 1..n，累加答案。

關鍵代碼片段

// 後綴數組構建 (倍增法 O(n log n))
// height 計算 (Kasai O(n))

ll ans = 0;
for (int L = 1; L <= n; ++L) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (height[i] >= L) {
            if (cnt == 0) ans++; // 新區間開始
            cnt++;
        } else {
            cnt = 0;
        }
    }
}
printf("%lld\n", ans);

複雜度

• 構建 SA：O(n log n) = 1000 × 10 = 10⁴。
• 枚舉 L 掃描 height：O(n²) = 10⁶，n=1000 可接受。
• 若 n=10000 需優化（如用 RMQ 或自動機），但本題 n≤1000 此法足夠。

易錯點

• `height` 數組下標：通常 `height[i]` = `sa[i]` 與 `sa[i-1]` 的 LCP，長度 n+1。
• 去重邏輯：連續 `height ≥ L` 區間每算一次 `ans++`，對應一個不同子串。
• 多測試案例輸入處理。

總結

HDU 3518 是「後綴數組統計重複子串」的基礎應用。枚舉長度 + 掃描 height 區間是直觀做法，n≤1000 時 O(n²) 完全可行。掌握 SA 構建與 height 含義，即可解決大多數子串統計問題。