後綴結構完全指南 — Suffix Array、Suffix Tree 與 LCP 陣列 | 資料結構與演算法
2026/07/21
後綴結構（Suffix Structures） 是字串演算法中最強大的索引家族，涵蓋 Suffix Array（後綴陣列）、LCP Array（最長公共前綴陣列） 與 Suffix Tree（後綴樹） 三大核心。透過對字串所有後綴建立有序索引，我們能在 O(m log n) 時間內完成模式匹配、求解 最長重複子字串、計算 不同子字串數量，甚至支援全文搜尋引擎的底層索引。本文將從基礎概念出發，逐步掌握 倍增法、SA-IS 線性建構、Kasai’s Algorithm 等核心技術，搭配 JavaScript/TypeScript 與 C++ 雙語言完整實作。
前言
在前一篇文章中，我們探討了近似與線上演算法如何在 NP-hard 問題與即時決策場景下找到「足夠好」的解。本篇我們將進入字串演算法的深水區—— 後綴結構（Suffix Structures）。
字串處理是程式開發中無處不在的需求：從搜尋引擎的全文檢索、IDE 的自動補全、到生物資訊學中的 DNA 序列比對，都仰賴高效的字串索引技術。暴力的子字串搜尋需要 O(nm) 時間，而 KMP、Z-Algorithm 等單模式匹配演算法雖然將複雜度降至 O(n+m)，卻無法高效處理「在同一文字上重複搜尋多個模式」的場景。
後綴結構 的核心思想是：對一個字串預先建立索引，之後每次查詢只需 O(m log n) 甚至 O(m) 的時間。這就像是為一本書建立「所有可能關鍵字」的索引——一旦索引建好，任何查詢都能快速完成。
學習本文後，你將能夠：
- 理解 Suffix Array、LCP Array、Suffix Tree 的定義與關聯
- 實作 倍增法 O(n log²n) 與 SA-IS O(n) 兩種 Suffix Array 建構法
- 使用 Kasai’s Algorithm 在 O(n) 時間建構 LCP 陣列
- 應用 Suffix Array 解決 模式匹配、最長重複子字串、最長公共子字串 等經典問題
- 認識 後綴自動機（SAM）、DC3 演算法 等進階變體
核心概念
後綴（Suffix）的基本概念
一個長度為 n 的字串 s，共有 n 個後綴。後綴 s[i..] 表示從位置 i 開始到字串結尾的子字串。
字串 s = "banana"（長度 n = 6，下標從 0 開始）
所有後綴：
i=0: "banana"
i=1: "anana"
i=2: "nana"
i=3: "ana"
i=4: "na"
i=5: "a"
觀察：任何子字串都是某個後綴的前綴
例如 "nan" = 後綴 "nana" 的前 3 個字元
→ 這就是後綴結構能支援子字串查詢的根本原因
Suffix Array（後綴陣列）
Suffix Array（SA） 是將字串所有後綴按 字典序 排列後，記錄各後綴的 起始下標 所形成的整數陣列。
s = "banana"
按字典序排列所有後綴：
SA[0] = 5 → "a"
SA[1] = 3 → "ana"
SA[2] = 1 → "anana"
SA[3] = 0 → "banana"
SA[4] = 4 → "na"
SA[5] = 2 → "nana"
Suffix Array: SA = [5, 3, 1, 0, 4, 2]
Rank Array（SA 的反函數）：rank[i] = 後綴 i 在 SA 中的位置
rank[0]=3, rank[1]=2, rank[2]=5
rank[3]=1, rank[4]=4, rank[5]=0
SA 的核心價值在於：後綴按字典序排列後，所有以相同子字串開頭的後綴會 聚集在一起，因此可以用 二分搜尋 在 O(m log n) 時間內找到任意模式。
LCP Array（最長公共前綴陣列）
LCP Array 記錄 Suffix Array 中 相鄰兩個後綴 的最長公共前綴（Longest Common Prefix）長度。lcp[i] 表示 SA[i] 和 SA[i-1] 對應後綴的 LCP 長度。
s = "banana"，SA = [5, 3, 1, 0, 4, 2]
相鄰後綴比較：
SA[0]=5: "a"
SA[1]=3: "ana" → LCP("a", "ana") = 1 → lcp[1] = 1
SA[2]=1: "anana" → LCP("ana", "anana") = 3 → lcp[2] = 3
SA[3]=0: "banana" → LCP("anana", "banana") = 0 → lcp[3] = 0
SA[4]=4: "na" → LCP("banana", "na") = 0 → lcp[4] = 0
SA[5]=2: "nana" → LCP("na", "nana") = 2 → lcp[5] = 2
LCP Array = [-, 1, 3, 0, 0, 2]
（lcp[0] 未定義，通常設為 0）
LCP 陣列的威力在於：
- 最長重複子字串 =
max(lcp[i])，對應位置為sa[argmax] - 不同子字串數量 =
n(n+1)/2 - sum(lcp[i]) - 搭配 Sparse Table（RMQ）預處理後，可在 O(1) 時間查詢任意兩個後綴的 LCP
Suffix Tree（後綴樹）概覽
Suffix Tree 是一棵壓縮的 Trie（Compressed Trie），將字串所有後綴插入後，合併僅有單一子節點的路徑。它在理論上非常優美：
Suffix Tree vs Suffix Array 對比：
特性 | Suffix Tree | Suffix Array + LCP
───────────────|────────────────────|──────────────────────
建構時間 | O(n)（Ukkonen） | O(n)（SA-IS）
空間 | ~20n bytes | ~8n bytes（SA + LCP）
模式匹配 | O(m) | O(m log n)
實作難度 | 極高 | 中等
快取效率 | 差（指標跳躍多） | 好（連續陣列）
競賽/面試常用 | 少 | 多
結論：Suffix Array + LCP 幾乎可以替代 Suffix Tree，
且實作更簡潔、空間更少、快取更友善。
本文以 Suffix Array + LCP 為主軸。
Ukkonen’s Algorithm 可在 O(n) 時間線上建構 Suffix Tree，但其實作極為複雜（需要處理 Active Point、Suffix Link、End Leaf 等機制），在面試和競賽中鮮少被要求手寫。因此本文將重點放在 Suffix Array + LCP 的實作與應用。
JavaScript / TypeScript 實作
Naive Suffix Array 建構
最直覺的做法是直接排序所有後綴。雖然時間複雜度較高（O(n² log n)，因為字串比較本身需要 O(n)），但有助於理解 SA 的本質：
// ─── Naive Suffix Array 建構 O(n² log n) ──────────────────────
function buildSuffixArrayNaive(s: string): number[] {
const n = s.length;
// 建立 (後綴起始下標, 後綴字串) 的配對
const suffixes = Array.from({ length: n }, (_, i) => i);
// 直接按後綴字串的字典序排序
suffixes.sort((a, b) => {
// 逐字元比較後綴 s[a..] 和 s[b..]
for (let k = 0; k < n - Math.min(a, b); k++) {
if (a + k >= n) return -1; // 較短的後綴排前面
if (b + k >= n) return 1;
if (s[a + k] < s[b + k]) return -1;
if (s[a + k] > s[b + k]) return 1;
}
return 0;
});
return suffixes;
}
// 測試
const s1 = "banana";
console.log("Naive SA:", buildSuffixArrayNaive(s1));
// 輸出：Naive SA: [5, 3, 1, 0, 4, 2]
倍增法建構 Suffix Array — O(n log²n)
倍增法（Prefix Doubling） 是競賽與面試中最實用的 SA 建構法，核心思想是：迭代地對「長度 2^k 的子字串」排序，每輪倍增子字串長度，利用上一輪的排名作為比較鍵。
// ─── 倍增法建構 Suffix Array O(n log²n) ──────────────────────
function buildSuffixArray(s: string): number[] {
const n = s.length;
// sa[i] = 字典序第 i 小的後綴的起始下標
let sa = Array.from({ length: n }, (_, i) => i);
// rank[i] = 後綴 i 的當前排名（初始為字元編碼）
let rank = Array.from({ length: n }, (_, i) => s.charCodeAt(i));
const tmp = new Array(n).fill(0);
for (let gap = 1; gap < n; gap <<= 1) {
// 比較函數：按 (rank[i], rank[i+gap]) 二元組排序
const compare = (a: number, b: number): number => {
if (rank[a] !== rank[b]) return rank[a] - rank[b];
const ra = a + gap < n ? rank[a + gap] : -1;
const rb = b + gap < n ? rank[b + gap] : -1;
return ra - rb;
};
sa.sort(compare);
// 根據新的排序更新 rank
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]];
if (compare(sa[i - 1], sa[i]) !== 0) tmp[sa[i]]++;
}
rank = [...tmp];
// 如果所有排名已唯一，提前結束
if (rank[sa[n - 1]] === n - 1) break;
}
return sa;
}
// 測試
const s2 = "banana";
const sa2 = buildSuffixArray(s2);
console.log("SA:", sa2);
// 輸出：SA: [5, 3, 1, 0, 4, 2]
演算法解析：
- 初始化：將每個字元的 ASCII 碼作為初始排名
- 倍增迭代：每輪將 gap 翻倍（1, 2, 4, 8…），使用
(rank[i], rank[i+gap])作為排序鍵 - 更新排名：排序後根據相鄰元素是否相同來更新 rank
- 提前終止：當所有排名都唯一時，SA 已確定
共 O(log n) 輪，每輪使用比較排序 O(n log n)，整體 O(n log²n)。若改用基數排序（Radix Sort），可優化至 O(n log n)。
SA-IS 線性建構 — O(n)
SA-IS（Suffix Array by Induced Sorting） 是目前最先進的線性 SA 建構演算法。其核心思想是將後綴分為 S 型（Smaller）和 L 型（Larger），找出 LMS（Left-Most S-type）後綴，遞迴求解子問題，再透過 Induced Sorting 推導完整 SA。
// ─── SA-IS 線性建構 Suffix Array O(n) ──────────────────────
function buildSuffixArraySAIS(s: string): number[] {
// 將字串轉為整數陣列，加入哨兵字元 0（字典序最小）
const arr = Array.from(s, (c) => c.charCodeAt(0) + 1);
arr.push(0); // 哨兵
const sa = sais(arr, Math.max(...arr) + 1);
// 移除哨兵對應的位置（SA[0] 固定是哨兵）
return sa.slice(1);
}
function sais(T: number[], alphabetSize: number): number[] {
const n = T.length;
if (n === 1) return [0];
if (n === 2) return T[0] < T[1] ? [0, 1] : [1, 0];
// Step 1: 分類每個後綴為 S 型或 L 型
const isS = new Uint8Array(n); // 1 = S型, 0 = L型
isS[n - 1] = 1; // 哨兵為 S 型
for (let i = n - 2; i >= 0; i--) {
if (T[i] < T[i + 1]) isS[i] = 1;
else if (T[i] > T[i + 1]) isS[i] = 0;
else isS[i] = isS[i + 1];
}
// 找出 LMS（Left-Most S-type）位置
const isLMS = (i: number) => i > 0 && isS[i] && !isS[i - 1];
const lmsPositions: number[] = [];
for (let i = 0; i < n; i++) {
if (isLMS(i)) lmsPositions.push(i);
}
// Step 2: 計算桶（Bucket）邊界
const getBuckets = (end: boolean): number[] => {
const count = new Array(alphabetSize).fill(0);
for (const c of T) count[c]++;
const buckets = new Array(alphabetSize).fill(0);
let sum = 0;
for (let i = 0; i < alphabetSize; i++) {
sum += count[i];
buckets[i] = end ? sum - 1 : sum - count[i];
}
return buckets;
};
// Induced Sort 核心函數
const inducedSort = (lms: number[]): number[] => {
const sa = new Array(n).fill(-1);
// 放置 LMS 後綴到桶的末端
let buckets = getBuckets(true);
for (let i = lms.length - 1; i >= 0; i--) {
sa[buckets[T[lms[i]]]--] = lms[i];
}
// 從左到右掃描，放置 L 型後綴
buckets = getBuckets(false);
for (let i = 0; i < n; i++) {
if (sa[i] > 0 && !isS[sa[i] - 1]) {
sa[buckets[T[sa[i] - 1]]++] = sa[i] - 1;
}
}
// 從右到左掃描，放置 S 型後綴
buckets = getBuckets(true);
for (let i = n - 1; i >= 0; i--) {
if (sa[i] > 0 && isS[sa[i] - 1]) {
sa[buckets[T[sa[i] - 1]]--] = sa[i] - 1;
}
}
return sa;
};
// Step 3: 第一次 Induced Sort（粗略排序 LMS）
let sa = inducedSort(lmsPositions);
// Step 4: 為 LMS 子字串命名
const lmsNames = new Map<number, number>();
let name = 0;
let prev = -1;
// 比較兩個 LMS 子字串是否相同
const lmsEqual = (a: number, b: number): boolean => {
for (let i = 0; ; i++) {
const aEnd = i > 0 && isLMS(a + i);
const bEnd = i > 0 && isLMS(b + i);
if (aEnd && bEnd) return true;
if (aEnd !== bEnd || T[a + i] !== T[b + i]) return false;
}
};
for (const pos of sa) {
if (!isLMS(pos)) continue;
if (prev === -1 || !lmsEqual(prev, pos)) name++;
lmsNames.set(pos, name);
prev = pos;
}
// Step 5: 若名稱不唯一，遞迴求解子問題
if (name < lmsPositions.length) {
const reducedT = lmsPositions.map((p) => lmsNames.get(p)!);
const reducedSA = sais(reducedT, name + 1);
// 用遞迴結果的排序順序重新排列 LMS 位置
const sortedLMS = reducedSA.map((i) => lmsPositions[i]);
sa = inducedSort(sortedLMS);
}
return sa;
}
// 測試
const s3 = "banana";
console.log("SA-IS:", buildSuffixArraySAIS(s3));
// 輸出：SA-IS: [5, 3, 1, 0, 4, 2]
// 驗證與倍增法結果一致
const s4 = "mississippi";
console.log("SA-IS:", buildSuffixArraySAIS(s4));
// 輸出：SA-IS: [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]
SA-IS 的優勢在於 嚴格 O(n) 時間與空間複雜度，適用於超長字串（如基因組序列，長度可達數十億）。
Kasai’s Algorithm — O(n) 建構 LCP 陣列
Kasai’s Algorithm 利用一個關鍵觀察來實現線性時間的 LCP 建構。
核心引理（LCP Lemma）：若後綴 s[i..] 與其在 SA 中前一個後綴的 LCP 長度為 h，則後綴 s[i+1..] 與其前一個後綴的 LCP 長度 >= h-1。
// ─── Kasai's Algorithm：O(n) 建構 LCP Array ──────────────────
function buildLCPArray(s: string, sa: number[]): number[] {
const n = s.length;
// 建立 rank 陣列（SA 的反函數）
const rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) rank[sa[i]] = i;
const lcp = new Array(n).fill(0);
let h = 0; // 當前 LCP 長度
for (let i = 0; i < n; i++) {
if (rank[i] > 0) {
const j = sa[rank[i] - 1]; // SA 中排在 s[i..] 前面的後綴
// 逐字元比較擴展 LCP
while (i + h < n && j + h < n && s[i + h] === s[j + h]) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) h--; // 關鍵：h 最多遞減 1
}
}
return lcp;
}
// 測試
const s5 = "banana";
const sa5 = buildSuffixArray(s5);
const lcp5 = buildLCPArray(s5, sa5);
console.log("字串:", s5);
console.log("SA:", sa5); // [5, 3, 1, 0, 4, 2]
console.log("LCP:", lcp5); // [0, 1, 3, 0, 0, 2]
為何 O(n)？ 變數 h 在整個迴圈中最多遞增 n 次（每次 while 迴圈成功匹配一個字元）、每次外迴圈最多遞減 1（共 n 次），因此 h 的總變化量為 O(n)。
模式匹配 — SA + 二分搜尋
利用 SA 的有序性質，可以用二分搜尋在 O(m log n) 時間內找到模式串 pattern 的所有出現位置。
// ─── SA + 二分搜尋模式匹配 O(m log n) ──────────────────────
function searchPattern(text: string, pattern: string, sa: number[]): number[] {
const n = text.length;
const m = pattern.length;
// 比較後綴 text[sa[mid]..] 的前 m 個字元與 pattern
const cmp = (mid: number): number => {
for (let i = 0; i < m && sa[mid] + i < n; i++) {
if (text[sa[mid] + i] < pattern[i]) return -1;
if (text[sa[mid] + i] > pattern[i]) return 1;
}
return sa[mid] + m <= n ? 0 : -1;
};
// 二分搜尋左邊界（第一個匹配位置）
let lo = 0, hi = n - 1, left = n;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (cmp(mid) >= 0) { left = mid; hi = mid - 1; }
else lo = mid + 1;
}
// 二分搜尋右邊界（最後一個匹配位置）
let right = -1;
lo = 0; hi = n - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (cmp(mid) <= 0) { right = mid; lo = mid + 1; }
else hi = mid - 1;
}
if (left > right) return []; // 未找到
return sa.slice(left, right + 1).sort((a, b) => a - b);
}
// 測試
const text1 = "mississippi";
const saText1 = buildSuffixArray(text1);
console.log('"issi" 出現位置:', searchPattern(text1, "issi", saText1));
// 輸出："issi" 出現位置: [1, 4]
console.log('"ssi" 出現位置:', searchPattern(text1, "ssi", saText1));
// 輸出："ssi" 出現位置: [2, 5]
console.log('"xyz" 出現位置:', searchPattern(text1, "xyz", saText1));
// 輸出："xyz" 出現位置: []
最長重複子字串（Longest Repeated Substring）
LCP 陣列的最大值即為最長重複子字串的長度，這是 SA + LCP 最經典的應用。
// ─── 最長重複子字串 ──────────────────────
function longestRepeatedSubstring(s: string): string {
const n = s.length;
if (n === 0) return "";
const sa = buildSuffixArray(s);
const lcp = buildLCPArray(s, sa);
let maxLen = 0;
let maxIdx = 0;
for (let i = 1; i < n; i++) {
if (lcp[i] > maxLen) {
maxLen = lcp[i];
maxIdx = sa[i];
}
}
return s.substring(maxIdx, maxIdx + maxLen);
}
// 測試
console.log(longestRepeatedSubstring("banana")); // "ana"
console.log(longestRepeatedSubstring("abcabc")); // "abc"
console.log(longestRepeatedSubstring("aaaaaa")); // "aaaaa"
console.log(longestRepeatedSubstring("abcdef")); // ""（無重複）
兩字串的最長公共子字串（Longest Common Substring）
將兩個字串用特殊分隔符拼接後建構 SA + LCP，再從 LCP 中找出分屬不同字串的相鄰後綴的最大 LCP 值。
// ─── 兩字串的最長公共子字串 ──────────────────────
function longestCommonSubstring(s1: string, s2: string): string {
// 用不出現在兩字串中的字元作為分隔符
const separator = "#";
const combined = s1 + separator + s2;
const n = combined.length;
const boundary = s1.length; // 分隔符位置
const sa = buildSuffixArray(combined);
const lcp = buildLCPArray(combined, sa);
let maxLen = 0;
let maxIdx = 0;
for (let i = 1; i < n; i++) {
// 檢查相鄰後綴是否分屬不同字串
const fromS1_curr = sa[i] < boundary;
const fromS1_prev = sa[i - 1] < boundary;
if (fromS1_curr !== fromS1_prev && lcp[i] > maxLen) {
maxLen = lcp[i];
maxIdx = sa[i];
}
}
return combined.substring(maxIdx, maxIdx + maxLen);
}
// 測試
console.log(longestCommonSubstring("abcdef", "xbcdey")); // "bcde"
console.log(longestCommonSubstring("ABABC", "BABCBA")); // "BABC"
console.log(longestCommonSubstring("hello", "world")); // "l"
C++ 對照
以下提供 C++ 版本的 Suffix Array + LCP 核心實作，方便需要在競賽或系統層面使用的讀者：
#include <bits/stdc++.h>
using namespace std;
// ─── O(n log²n) 倍增法建構 Suffix Array ──────────────────────
vector<int> buildSuffixArray(const string& s) {
int n = s.size();
vector<int> sa(n), rank_(n), tmp(n);
iota(sa.begin(), sa.end(), 0);
for (int i = 0; i < n; i++) rank_[i] = s[i];
for (int gap = 1; gap < n; gap <<= 1) {
auto cmp = [&](int a, int b) {
if (rank_[a] != rank_[b]) return rank_[a] < rank_[b];
int ra = (a + gap < n) ? rank_[a + gap] : -1;
int rb = (b + gap < n) ? rank_[b + gap] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
}
rank_ = tmp;
if (rank_[sa[n-1]] == n-1) break;
}
return sa;
}
// ─── Kasai's Algorithm：O(n) 建構 LCP Array ──────────────────
vector<int> buildLCP(const string& s, const vector<int>& sa) {
int n = s.size();
vector<int> rank_(n), lcp(n, 0);
for (int i = 0; i < n; i++) rank_[sa[i]] = i;
for (int i = 0, h = 0; i < n; i++) {
if (rank_[i] > 0) {
int j = sa[rank_[i] - 1];
while (i + h < n && j + h < n && s[i+h] == s[j+h]) h++;
lcp[rank_[i]] = h;
if (h) h--;
}
}
return lcp;
}
// ─── 模式匹配（二分搜尋）──────────────────────
vector<int> searchPattern(const string& text, const string& pat,
const vector<int>& sa) {
int n = text.size(), m = pat.size();
auto cmp = [&](int mid) -> int {
return text.compare(sa[mid], min(m, n - sa[mid]), pat);
};
// 左邊界
int lo = 0, hi = n - 1, left = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (cmp(mid) >= 0) { left = mid; hi = mid - 1; }
else lo = mid + 1;
}
// 右邊界
int right = -1;
lo = 0; hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (cmp(mid) <= 0) { right = mid; lo = mid + 1; }
else hi = mid - 1;
}
vector<int> result;
if (left <= right) {
for (int i = left; i <= right; i++) result.push_back(sa[i]);
sort(result.begin(), result.end());
}
return result;
}
// ─── 最長重複子字串 ──────────────────────
string longestDupSubstring(const string& s) {
auto sa = buildSuffixArray(s);
auto lcp = buildLCP(s, sa);
int maxLen = 0, maxIdx = 0;
for (int i = 1; i < (int)s.size(); i++) {
if (lcp[i] > maxLen) {
maxLen = lcp[i];
maxIdx = sa[i];
}
}
return s.substr(maxIdx, maxLen);
}
int main() {
string s = "banana";
auto sa = buildSuffixArray(s);
auto lcp = buildLCP(s, sa);
cout << "SA: ";
for (int x : sa) cout << x << " ";
cout << "\nLCP: ";
for (int x : lcp) cout << x << " ";
cout << "\n最長重複子串: " << longestDupSubstring(s) << "\n";
// 輸出：
// SA: 5 3 1 0 4 2
// LCP: 0 1 3 0 0 2
// 最長重複子串: ana
// 模式匹配
string text = "mississippi";
auto sa2 = buildSuffixArray(text);
auto pos = searchPattern(text, "issi", sa2);
cout << "\"issi\" 出現位置: ";
for (int p : pos) cout << p << " ";
cout << "\n";
// 輸出："issi" 出現位置: 1 4
return 0;
}
複雜度分析
| 結構 / 操作 | 建構時間 | 查詢時間 | 空間 | 備註 |
|---|---|---|---|---|
| SA（Naive） | O(n² log n) | O(m log n) | O(n) | 僅用於教學 |
| SA（倍增法） | O(n log²n) | O(m log n) | O(n) | 競賽/面試首選 |
| SA（SA-IS） | O(n) | O(m log n) | O(n) | 超長字串使用 |
| LCP（Kasai） | O(n) | — | O(n) | 需先有 SA |
| RMQ（Sparse Table） | O(n log n) | O(1) | O(n log n) | 任意兩後綴 LCP |
| Suffix Tree（Ukkonen） | O(n) | O(m) | O(n)，常數大 | 實作極複雜 |
| 後綴自動機（SAM） | O(n) | O(m) | O(n) | 線上建構 |
關鍵觀察：
- 倍增法 O(n log²n) 在 n <= 10^5 時綽綽有餘，是性價比最高的選擇
- SA-IS O(n) 在 n > 10^6 時才有明顯優勢，但實作複雜度顯著增加
- LCP 陣列 搭配 Sparse Table 後可在 O(1) 時間查詢任意兩個後綴的 LCP，是許多進階應用的基礎
變體與延伸
後綴自動機（Suffix Automaton, SAM）
後綴自動機 是識別字串所有子字串的 最小有限自動機，節點數 O(n)、邊數 O(n)，可線上（逐字元）建構。
SAM 核心概念：
節點 = endpos 等價類
endpos(t) = {t 在 s 中出現的所有結束位置}
endpos 相同的子字串歸為同一節點
例：s = "abbc"
"b" → endpos = {2, 3}
"bb" → endpos = {3}
Suffix Link：每個節點指向最長真後綴所在節點，形成一棵樹
典型應用：
1. 不同子字串數量：O(n) — 遍歷所有節點，加總 (len - link.len)
2. 最長公共子字串：O(n+m) — 在 SAM 上跑另一字串
3. 子字串出現次數：O(n) — endpos 集合大小
4. 最短唯一子字串：O(n)
Enhanced Suffix Array（增強後綴陣列）
Enhanced Suffix Array 是指 SA + LCP 再加上額外的輔助陣列（如 child table、suffix link table），使其功能完全等價於 Suffix Tree，而空間僅需約 8n bytes（相比 Suffix Tree 的 20n+）。
DC3 / Skew Algorithm
DC3（Difference Cover of 3） 也稱 Skew Algorithm，是另一種 O(n) 的 SA 建構法。其核心思想是：
- 將後綴分為三組：位置 mod 3 = 0, 1, 2
- 先遞迴排序 mod 3 != 0 的後綴（佔 2/3）
- 再利用結果推導 mod 3 = 0 的後綴排序
- 最後合併三組結果
DC3 的優勢在於概念比 SA-IS 更直覺，且同樣達到 O(n) 時間。在並行計算（Parallel Computing）場景下，DC3 比 SA-IS 更容易並行化。
面試考點
後綴結構在面試中的考察重點集中在以下幾個方面：
面試高頻考點：
1. Suffix Array 建構原理
→ 倍增法的時間複雜度分析
→ 為何每輪可以利用上一輪的排名？
2. LCP Array 應用
→ 最長重複子字串 = max(LCP)
→ 不同子字串數量 = n(n+1)/2 - Σlcp[i]
→ 任意兩後綴 LCP = RMQ on LCP Array
3. 模式匹配
→ 為何可以用二分搜尋？（SA 的有序性質）
→ 時間複雜度：O(m log n)
4. 與其他字串演算法的比較
→ SA vs KMP：SA 適合多次查詢，KMP 適合單次匹配
→ SA vs Trie：SA 更省空間，Trie 更適合前綴查詢
→ SA vs Hash：SA 無碰撞風險，Hash 更簡單
5. 實際應用場景
→ 全文搜尋引擎索引
→ DNA 序列比對
→ 資料壓縮（BWT）
→ 防抄襲偵測（Longest Common Substring）
LeetCode 實戰
LeetCode 1044 — Longest Duplicate Substring（困難）
題目：給定字串 s，找出最長的重複子字串（至少出現兩次）。若不存在返回空字串。
// ─── LeetCode 1044：Suffix Array + LCP 解法 ──────────────────
function longestDupSubstring(s: string): string {
const n = s.length;
// 建構 Suffix Array（倍增法）
let sa = Array.from({ length: n }, (_, i) => i);
let rank = Array.from({ length: n }, (_, i) => s.charCodeAt(i));
const tmp = new Array(n).fill(0);
for (let gap = 1; gap < n; gap <<= 1) {
const cmp = (a: number, b: number) => {
if (rank[a] !== rank[b]) return rank[a] - rank[b];
const ra = a + gap < n ? rank[a + gap] : -1;
const rb = b + gap < n ? rank[b + gap] : -1;
return ra - rb;
};
sa.sort(cmp);
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) !== 0 ? 1 : 0);
}
rank = [...tmp];
if (rank[sa[n - 1]] === n - 1) break;
}
// 建構 LCP Array（Kasai's Algorithm）
const rankArr = new Array(n).fill(0);
for (let i = 0; i < n; i++) rankArr[sa[i]] = i;
const lcp = new Array(n).fill(0);
let h = 0;
for (let i = 0; i < n; i++) {
if (rankArr[i] > 0) {
const j = sa[rankArr[i] - 1];
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
lcp[rankArr[i]] = h;
if (h > 0) h--;
}
}
// 找 LCP 最大值
let maxLen = 0, maxIdx = 0;
for (let i = 1; i < n; i++) {
if (lcp[i] > maxLen) {
maxLen = lcp[i];
maxIdx = sa[i];
}
}
return s.substring(maxIdx, maxIdx + maxLen);
}
// 測試
console.log(longestDupSubstring("banana")); // "ana"
console.log(longestDupSubstring("abcd")); // ""
/*
時間：O(n log²n)
空間：O(n)
*/
LeetCode 1316 — Distinct Echo Substrings（困難）
題目：找出字串中所有 Echo 子字串的數量。Echo 子字串定義為長度為偶數 2k，且前半等於後半。
// ─── LeetCode 1316：SA + LCP + RMQ 解法 ──────────────────
function distinctEchoSubstrings(s: string): number {
const n = s.length;
const sa = buildSuffixArray(s);
const lcp = buildLCPArray(s, sa);
const rankArr = new Array(n).fill(0);
for (let i = 0; i < n; i++) rankArr[sa[i]] = i;
// Sparse Table 預處理 RMQ
const LOG = Math.floor(Math.log2(n)) + 1;
const sparse: number[][] = Array.from(
{ length: LOG }, () => new Array(n).fill(0)
);
for (let i = 0; i < n; i++) sparse[0][i] = lcp[i];
for (let j = 1; j < LOG; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
sparse[j][i] = Math.min(
sparse[j - 1][i],
sparse[j - 1][i + (1 << (j - 1))]
);
}
}
// O(1) 查詢兩後綴的 LCP
const queryLCP = (a: number, b: number): number => {
let ra = rankArr[a], rb = rankArr[b];
if (ra > rb) [ra, rb] = [rb, ra];
if (ra === rb) return n - a;
const k = Math.floor(Math.log2(rb - ra));
return Math.min(sparse[k][ra + 1], sparse[k][rb - (1 << k) + 1]);
};
// 用 Set 去重（透過滾動雜湊）
const MOD = BigInt("1000000000000000009");
const BASE = 131n;
const pow = new Array(n + 1).fill(0n);
pow[0] = 1n;
for (let i = 1; i <= n; i++) pow[i] = (pow[i - 1] * BASE) % MOD;
const ph = new Array(n + 1).fill(0n);
for (let i = 0; i < n; i++) {
ph[i + 1] = (ph[i] * BASE + BigInt(s.charCodeAt(i))) % MOD;
}
const getHash = (l: number, r: number) =>
((ph[r + 1] - ph[l] * pow[r - l + 1]) % MOD + MOD) % MOD;
const seen = new Set<bigint>();
let count = 0;
for (let k = 1; k * 2 <= n; k++) {
for (let i = 0; i + k * 2 <= n; i++) {
if (queryLCP(i, i + k) >= k) {
const h = getHash(i, i + 2 * k - 1);
if (!seen.has(h)) {
seen.add(h);
count++;
}
}
}
}
return count;
}
// 測試
console.log(distinctEchoSubstrings("abcabcabc")); // 3
console.log(distinctEchoSubstrings("leetcodeleetcode")); // 2
/*
時間：O(n²)（枚舉所有半長 k 和起始位置 i）
空間：O(n log n)（Sparse Table）
*/
LeetCode 1698 — Number of Distinct Substrings in a String（中等）
題目：計算字串中不同子字串的數量。
// ─── LeetCode 1698：SA + LCP 計算不同子字串數量 ──────────────
function countDistinctSubstrings(s: string): number {
const n = s.length;
const sa = buildSuffixArray(s);
const lcp = buildLCPArray(s, sa);
// 不同子字串數量 = 所有子字串數量 - 重複的部分
// = n(n+1)/2 - Σlcp[i]
let total = (n * (n + 1)) / 2;
for (let i = 1; i < n; i++) {
total -= lcp[i];
}
return total; // 不含空字串；若需含空字串，return total + 1
}
// 測試
console.log(countDistinctSubstrings("banana")); // 15
console.log(countDistinctSubstrings("aaa")); // 3（"a", "aa", "aaa"）
console.log(countDistinctSubstrings("abcd")); // 10
/*
公式推導：
每個後綴 sa[i] 貢獻 (n - sa[i]) 個子字串
但與前一個後綴重複了 lcp[i] 個
淨貢獻 = (n - sa[i]) - lcp[i]
加總 = Σ(n - sa[i]) - Σlcp[i]
= n(n+1)/2 - Σlcp[i]
時間：O(n log²n)（SA 建構）
空間：O(n)
*/
LeetCode 5 — Longest Palindromic Substring（中等）
雖然此題更常用 Manacher’s Algorithm 或 DP 解法，但也可以用 SA + LCP 的思路：最長回文子字串等於原字串與其反轉字串的最長公共子字串（加上位置約束）。
// ─── LeetCode 5：SA + LCP 思路（概念示範）──────────────────
function longestPalindromeSA(s: string): string {
const n = s.length;
// 拼接：s + "#" + reverse(s)
const rev = s.split("").reverse().join("");
const combined = s + "#" + rev;
const totalLen = combined.length;
const sa = buildSuffixArray(combined);
const lcp = buildLCPArray(combined, sa);
let maxLen = 1;
let start = 0;
for (let i = 1; i < totalLen; i++) {
// 相鄰後綴必須一個來自 s、一個來自 reverse(s)
const pos1 = sa[i], pos2 = sa[i - 1];
const from1 = pos1 < n, from2 = pos2 < n;
if (from1 === from2) continue; // 來自同一字串，跳過
const lcpVal = lcp[i];
if (lcpVal <= maxLen) continue;
// 驗證是否形成回文（位置約束）
const origPos = from1 ? pos1 : pos2;
const revPos = from1 ? pos2 : pos1;
// revPos 在反轉字串中的對應原始位置
const origEnd = totalLen - 1 - revPos;
// 奇數長度回文：origPos + lcpVal - 1 == origEnd
// 偶數長度回文：origPos + lcpVal == origEnd + 1
if (origPos + lcpVal - 1 === origEnd || origPos + lcpVal === origEnd + 1) {
if (lcpVal > maxLen) {
maxLen = lcpVal;
start = origPos;
}
}
}
return s.substring(start, start + maxLen);
}
// 注意：此方法需要更精細的位置檢查。
// 面試中回文問題建議優先使用 Manacher's Algorithm 或 DP。
總結
本文深入介紹了 後綴結構 這一字串演算法中最強大的索引家族：
- Suffix Array 是後綴結構的核心，將所有後綴按字典序排列後記錄起始下標，支援 O(m log n) 模式匹配
- LCP Array 記錄相鄰後綴的最長公共前綴長度，是求解最長重複子字串、計算不同子字串數量的關鍵
- 倍增法 O(n log²n) 是建構 SA 的最佳性價比選擇，平衡了實作難度與效率
- SA-IS O(n) 適用於超長字串場景，但實作複雜度顯著增加
- Kasai’s Algorithm 利用 LCP Lemma 在 O(n) 時間建構 LCP 陣列
- Suffix Tree 在理論上功能最豐富，但 SA + LCP 幾乎可以完全替代，且空間與實作更優
後綴結構的核心思維是 「預處理換查詢」——花一次 O(n log n) 或 O(n) 的建構成本，換取無限次 O(m log n) 的高效查詢。這種以空間和預處理時間換取查詢效率的設計理念，在資料庫索引、搜尋引擎、壓縮算法等領域都有廣泛應用。
下一篇文章，我們將探討 持久化資料結構（Persistent Data Structures）——如何在不修改原始資料結構的情況下保存每次操作的歷史版本，實現高效的「時間旅行」功能。
系列導覽：