題目
給定字串 s，線上建構 Suffix Automaton（SAM）。實作 extend(c)，說明每個狀態的 len、link、轉移與 endpos 含義，並用它計算不同子串數量、模式出現次數或最長共同子串。要求解釋為什麼狀態數是 O(n)，以及何時必須建立 clone。
面試官考察點
- 能否把狀態解釋成一組具有相同
endpos的子串，而不是普通 Trie 節點。 - 能否正確區分連續轉移、直接連結和 clone 三種建構分支。
- 能否維護
len[link[v]] < len[v]、轉移確定性和 suffix-link 樹不變量。 - 能否把結構性質轉成計數、匹配和複雜度結論。
參考答案
SAM 是辨識原字串所有子串的最小部分 DFA。狀態 v 保存該等價類中最長子串長度 len[v]，link[v] 指向最長的、屬於另一等價類的後綴。狀態代表的長度區間是 (len[link[v]], len[v]]，所以一個狀態可以涵蓋多個不同長度的子串。
追加字元時先建立 cur，沿 suffix link 向後尋找缺少該轉移的狀態並補邊。若遇到已有狀態 q 且 len[p]+1 == len[q]，直接令 link[cur]=q；若不相等，複製 q 的轉移建立 clone，把 clone 的 len 設為 len[p]+1，再沿 suffix link 把指向 q 的相關邊改到 clone，並令 link[q] 與 link[cur] 都指向 clone。clone 保證每個狀態的長度區間連續。
所有非根狀態對不同子串的貢獻是 len[v] - len[link[v]]。若先給原字串前綴對應狀態計數 1，再按 len 降序把計數累加到 link，即可得到每個等價類的出現次數。
實作範例
下面的偽代碼展示核心建構；轉移可以用雜湊表或有序映射。
extend(c):
cur = new state
len[cur] = len[last] + 1
p = last
while p != -1 and c not in next[p]:
next[p][c] = cur
p = link[p]
if p == -1:
link[cur] = root
else:
q = next[p][c]
if len[p] + 1 == len[q]:
link[cur] = q
else:
clone = copy(q)
len[clone] = len[p] + 1
while p != -1 and next[p][c] == q:
next[p][c] = clone
p = link[p]
link[q] = link[cur] = clone
last = cur計算不同子串數量時遍歷非根狀態累加 len[v] - len[link[v]]。計算模式出現次數時沿轉移走到對應狀態，再讀取按長度降序傳播後的計數。
常見誤區
- 把 SAM 當成只接受後綴的普通 Trie，忽略它實際壓縮了所有子串的
endpos等價類。 - clone 複製了轉移卻忘記複製或重新設定
link，導致後續長度區間斷裂。 - 修改轉移時沒有沿 suffix link 回溯到第一個不再指向
q的狀態。 - 給 clone 計入一次前綴出現次數，造成所有出現次數偏大。
- 用固定陣列儲存巨大字元集，卻沒有說明空間成本和字元編碼邊界。
複雜度取捨
在固定字母表或雜湊轉移下，建構時間和空間為 O(n)，狀態最多約 2n-1。若每個狀態的轉移使用平衡樹，複雜度會增加到與字母表操作相關的對數因子。SAM 適合固定文本上的大量子串查詢；需要字典序遍歷、LCP 或後綴排序時，後綴陣列可能更易控制記憶體和存取區域性。
SAM 的線性上界依賴線上追加模型。若要在字串中間插入、刪除或雙端更新，通常需要不同結構，不能直接沿用 extend 的不變量。
先用空字串、單字元、重複字元和觸發 clone 的 abbb 做逐步斷言，再隨機生成字串，與暴力集合比較不同子串數量和模式出現次數。最長共同子串測試可把第二個字串逐字元送入 SAM，並在失配時沿 suffix link 回退。
參考資料
- CP-algorithms 的 SAM 講義：狀態區間、clone 建構和查詢公式。
- Blumer 等人的最小子串自動機論文：狀態與轉移上界的理論來源。
- Carnegie Mellon 字串演算法講義：後綴陣列與後綴自動機的適用場景比較。
追問
為什麼每個狀態代表連續長度區間？
同一 endpos 等價類中的子串按長度排列時不會出現空洞；最長子串的後綴會逐步落入包含它的更大等價類。link 指向區間左側的邊界，因此區間正好是 (len[link[v]], len[v]]。
什麼時候必須建立 clone？
當已有轉移目標 q 的 len[q] 大於 len[p]+1 時，q 同時承載了兩個不連續的長度範圍。複製轉移並把邊界拆出 clone，才能恢復連續區間不變量。
為什麼不同子串數量是這些區間長度的總和？
每個狀態涵蓋的長度區間不重疊，且區間中的每個長度對應一個不同子串。把每個狀態的區間大小相加，就得到全部非空不同子串數。
SAM 與 Aho–Corasick 如何選擇？
SAM 面向一個文本的全部子串結構和多種統計；Aho–Corasick 面向一組已知模式在文本中的批量匹配。需求是模式集合固定還是文本結構固定，決定了建構方向。
如何擴展到最長共同子串？
先為字串 S 建 SAM，再掃描 T。沿轉移前進並維護目前匹配長度；失配時沿 suffix link 回退並繼續嘗試，記錄過程中出現的最大長度即可。