字串問題的終極武器不是 KMP，是 Suffix Array——一旦建好，幾乎所有字串查詢都能用二分搜尋解決。
為什麼需要它？
KMP 能找一個 pattern，但如果要做「最長重複子字串」「兩個字串的最長公共子字串」「字串裡有多少個不同子字串」，KMP 就不夠了。
後綴樹（Suffix Tree）可以處理，但實作複雜且常數大。Suffix Array 是後綴樹的「壓縮版」——用一個整數陣列存所有後綴的字典序排名，空間更省，搭配 LCP 陣列幾乎能解決所有後綴樹能解的問題。
核心結構
Suffix Array（SA）：把字串所有後綴按字典序排序，記錄每個後綴的起始索引。
s = "banana"
後綴： 字典序排序：
0: banana → 5: a
1: anana 3: ana
2: nana 1: anana
3: ana 0: banana
4: na 4: na
5: a 2: nana
SA = [5, 3, 1, 0, 4, 2]LCP 陣列：SA 中相鄰兩個後綴的最長公共前綴長度。
SA = [5, 3, 1, 0, 4, 2]
a ana anana banana na nana
LCP = [0, 1, 3, 0, 0, 2]
↑ ↑
ana/anana na/nana
共同前綴3 共同前綴2建構：倍增法 O(n log² n)
每一輪把排名 key 的長度翻倍——先按 1 個字元排，再按 2 個字元，再按 4 個……log n 輪後全部後綴的相對排名確定。
round 0: 按 1 字元排 → [a, a, a, b, n, n]
round 1: 按前 2 字元排 → [a, an, an, ba, na, na]（利用 round 0 排名）
...LCP 陣列用 Kasai 演算法 O(n) 線性建構，利用「相鄰後綴的 LCP 至少是上一個 LCP - 1」的性質。
應用
// 模式搜尋 O(m log n)
// 在 SA 上二分：找到所有以 pattern 為前綴的後綴
int lo = lowerBound(sa, s, pattern);
int hi = upperBound(sa, s, pattern);
// SA[lo..hi] 的後綴都以 pattern 開頭，共 hi-lo+1 個出現位置| 問題 | 解法 | 複雜度 |
|---|---|---|
| 模式搜尋 | SA 上二分 | O(m log n) |
| 最長重複子字串 | LCP 陣列最大值 | O(n) |
| 不同子字串數量 | n(n+1)/2 − sum(LCP) | O(n) |
| 兩字串最長公共子字串 | 合併後建 SA，找跨分隔符的最大 LCP | O(n log n) |
複雜度
| 時間 | 空間 | |
|---|---|---|
| 建 SA（倍增） | O(n log² n) | O(n) |
| 建 SA（SA-IS） | O(n) | O(n) |
| 建 LCP（Kasai） | O(n) | O(n) |
| 模式搜尋 | O(m log n) | — |
SA-IS 是線性建構演算法，實作複雜但競賽常見。面試和一般工程用倍增法就夠。
🎬 互動視覺化：Suffix Array 建構與 LCP 對照 — 輸入一個字串，看所有後綴怎麼被排成 SA、相鄰兩條的 LCP 又是怎麼算出來的，「排序換查詢」的預處理成本瞬間變具體。
Suffix Array 是字串世界的「預處理換查詢」——建一次，幾乎所有字串查詢都能 O(log n) 或 O(1) 回答。
接下來往哪走
- Computational Geometry 計算幾何基礎 — 下一篇：從字串切到平面幾何，叉積是一切的起點
- Rolling Hash 滾動雜湊：O(1) 的子字串比較 — 子字串比較的另一條路：不排序後綴，用雜湊直接比
- String Algorithms 字串演算法 — KMP、Z Algorithm 這些單模式匹配的基礎在這裡