後綴自動機 (SAM)

一些前置約定/定義

記 \(\Sigma\) 為字符集，\(\left|\Sigma\right|\) 為字符集大小。對於一個字符串 \(s\)，記 \(\left|s\right|\) 為其長度。

後綴自動機概述

後綴自動機(suffix automaton, SAM) 是一個能解決許多字符串相關問題的有力的數據結構。

舉個例子，以下的字符串問題都可以在線性時間內通過 SAM 解決。

在另一個字符串中搜索一個字符串的所有出現位置。
計算給定的字符串中有多少個不同的子串。

直觀上，字符串的 SAM 可以理解為給定字符串的 所有子串 的壓縮形式。值得注意的事實是，SAM 將所有的這些信息以高度壓縮的形式儲存。對於一個長度為 \(n\) 的字符串，它的空間複雜度僅為 \(O(n)\)。此外，構造 SAM 的時間複雜度僅為 \(O(n)\)。準確地説，一個 SAM 最多有 \(2n-1\) 個節點和 \(3n-4\) 條轉移邊。

定義

字符串 \(s\) 的 SAM 是一個接受 \(s\) 的所有後綴的最小 DFA（確定性有限自動機或確定性有限狀態自動機）。

換句話説：

SAM 是一張有向無環圖。結點被稱作狀態，邊被稱作狀態間的轉移。
圖存在一個源點 \(t_0\)，稱作 初始狀態，其它各結點均可從 \(t_0\) 出發到達。
每個轉移都標有一些字母。從一個結點出發的所有轉移均不同。
存在一個或多個 終止狀態。如果我們從初始狀態 \(t_0\) 出發，最終轉移到了一個終止狀態，則路徑上的所有轉移連接起來一定是字符串 \(s\) 的一個後綴。\(s\) 的每個後綴均可用一條從 \(t_0\) 到某個終止狀態的路徑構成。
在所有滿足上述條件的自動機中，SAM 的結點數是最少的。

子串的性質

SAM 最簡單、也最重要的性質是，它包含關於字符串 \(s\) 的所有子串的信息。任意從初始狀態 \(t_0\) 開始的路徑，如果我們將轉移路徑上的標號寫下來，都會形成 \(s\) 的一個子串。反之每個 \(s\) 的子串對應從 \(t_0\) 開始的某條路徑。

為了簡化表達，我們稱子串對應一條路徑（從 \(t_0\) 開始、由一些標號構成這個子串）。反過來，我們説任意一條路徑對應它的標號構成的字符串。

到達某個狀態的路徑可能不止一條，因此我們説一個狀態對應一些字符串的集合，這個集合的每個元素對應這些路徑。

構建過程

我們將會在這裏展示一些簡單的字符串的後綴自動機。

我們用藍色表示初始狀態，用綠色表示終止狀態。

對於字符串 \(s=\varnothing\)：

對於字符串 \(s=\texttt{a}\)：

對於字符串 \(s=\texttt{aa}\)：

對於字符串 \(s=\texttt{ab}\)：

對於字符串 \(s=\texttt{abb}\)：

對於字符串 \(s=\texttt{abbb}\)：

在線性時間內構造

在我們描述線性時間內構造 SAM 的算法之前，我們需要引入幾個對理解構造過程非常重要的概念並對其進行簡單證明。

結束位置 `endpos`

考慮字符串 \(s\) 的任意非空子串 \(t\)，我們記 \(\operatorname{endpos}(t)\) 為在字符串 \(s\) 中 \(t\) 的所有結束位置（假設對字符串中字符的編號從零開始）。例如，對於字符串 \(\texttt{abcbc}\)，我們有 \(\operatorname{endpos}(\texttt{bc})=2,\,4\)。

兩個子串 \(t_1\) 與 \(t_2\) 的 \(\operatorname{endpos}\) 集合可能相等：\(\operatorname{endpos}(t_1)=\operatorname{endpos}(t_2)\)。這樣所有字符串 \(s\) 的非空子串都可以根據它們的 \(\operatorname{endpos}\) 集合被分為若干 等價類。

顯然，SAM 中的每個狀態對應一個或多個 \(\operatorname{endpos}\) 相同的子串。換句話説，SAM 中的狀態數等於所有子串的等價類的個數，再加上初始狀態。SAM 的狀態個數等價於 \(\operatorname{endpos}\) 相同的一個或多個子串所組成的集合的個數 \(+1\)。

我們稍後將會用這個假設來介紹構造 SAM 的算法。我們將發現，SAM 需要滿足的所有性質，除了最小性以外都滿足了。由 Nerode 定理我們可以得出最小性（不會在這篇文章中證明）。

由 \(\operatorname{endpos}\) 的值我們可以得到一些重要結論：

引理 1： 字符串 \(s\) 的兩個非空子串 \(u\) 和 \(w\)（假設 \(\left|u\right|\le \left|w\right|\)）的 \(\operatorname{endpos}\) 相同，當且僅當字符串 \(u\) 在 \(s\) 中的每次出現，都是以 \(w\) 後綴的形式存在的。

引理顯然成立。如果 \(u\) 和 \(w\) 的 \(\operatorname{endpos}\) 相同，則 \(u\) 是 \(w\) 的一個後綴，且只以 \(s\) 中的一個 \(w\) 的後綴的形式出現。且根據定義，如果 \(u\) 為 \(w\) 的一個後綴，且只以後綴的形式在 \(s\) 中出現時，兩個子串的 \(\operatorname{endpos}\) 相同。

引理 2： 考慮兩個非空子串 \(u\) 和 \(w\)（假設 \(\left|u\right|\le \left|w\right|\)）。那麼要麼 \(\operatorname{endpos}(u)\cap \operatorname{endpos}(w)=\varnothing\)，要麼 \(\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)\)，取決於 \(u\) 是否為 \(w\) 的一個後綴：

\[ \begin{cases} \operatorname{endpos}(w) \subseteq \operatorname{endpos}(u) & \text{if } u \text{ is a suffix of } w \\ \operatorname{endpos}(w) \cap \operatorname{endpos}(u) = \varnothing & \text{otherwise} \end{cases} \]

證明：如果集合 \(\operatorname{endpos}(u)\) 與 \(\operatorname{endpos}(w)\) 有至少一個公共元素，那麼由於字符串 \(u\) 與 \(w\) 在相同位置結束，\(u\) 是 \(w\) 的一個後綴。所以在每次 \(w\) 出現的位置，子串 \(u\) 也會出現。所以 \(\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)\)。

引理 3： 考慮一個 \(\operatorname{endpos}\) 等價類，將類中的所有子串按長度非遞增的順序排序。每個子串都不會比它前一個子串長，與此同時每個子串也是它前一個子串的後綴。換句話説，對於同一等價類的任一兩子串，較短者為較長者的後綴，且該等價類中的子串長度恰好覆蓋整個區間 \([x,y]\)。

證明

如果 \(\operatorname{endpos}\) 等價類中只包含一個子串，引理顯然成立。現在我們來討論子串元素個數大於 \(1\) 的等價類。

由引理 1，兩個不同的 \(\operatorname{endpos}\) 等價的字符串中，較短者總是較長者的真後綴。因此，等價類中沒有等長的字符串。

記 \(w\) 為等價類中最長的字符串、\(u\) 為等價類中最短的字符串。由引理 1，字符串 \(u\) 是字符串 \(w\) 的真後綴。現在考慮長度在區間 \([\left|u\right|,\left|w\right|]\) 中的 \(w\) 的任意後綴。容易看出，這個後綴也在同一等價類中，因為這個後綴只能在字符串 \(s\) 中以 \(w\) 的一個後綴的形式存在（也因為較短的後綴 \(u\) 在 \(s\) 中只以 \(w\) 的後綴的形式存在）。因此，由引理 1，這個後綴和字符串 \(w\) 的 \(\operatorname{endpos}\) 相同。

後綴鏈接 `link`

考慮 SAM 中某個不是 \(t_0\) 的狀態 \(v\)。我們已經知道，狀態 \(v\) 對應於具有相同 \(\operatorname{endpos}\) 的等價類。我們如果定義 \(w\) 為這些字符串中最長的一個，則所有其它的字符串都是 \(w\) 的後綴。

我們還知道字符串 \(w\) 的前幾個後綴（按長度降序考慮）全部包含於這個等價類，且所有其它後綴（至少有一個——空後綴）在其它的等價類中。我們記 \(t\) 為最長的這樣的後綴，然後將 \(v\) 的後綴鏈接連到 \(t\) 上。

換句話説，一個 後綴鏈接 \(\operatorname{link}(v)\) 連接到對應於 \(w\) 的最長後綴的另一個 \(\operatorname{endpos}\) 等價類的狀態。

以下我們假設初始狀態 \(t_0\) 對應於它自己這個等價類（只包含一個空字符串）。為了方便，我們規定 \(\operatorname{endpos}(t_0)=\{-1,0,\ldots,\left|S\right|-1\}\)。

引理 4： 所有後綴鏈接構成一棵根節點為 \(t_0\) 的樹。

證明：考慮任意不是 \(t_0\) 的狀態 \(v\)，後綴鏈接 \(\operatorname{link}(v)\) 連接到的狀態對應於嚴格更短的字符串（後綴鏈接的定義、引理 3）。因此，沿後綴鏈接移動，我們總是能到達對應空串的初始狀態 \(t_0\)。

引理 5： 通過 \(\operatorname{endpos}\) 集合構造的樹（每個子節點的 \(\textit{subset}\) 都包含在父節點的 \(\textit{subset}\) 中）與通過後綴鏈接 \(\operatorname{link}\) 構造的樹相同。

證明：由引理 2，任意一個 SAM 的 \(\operatorname{endpos}\) 集合形成了一棵樹（因為兩個集合要麼完全沒有交集要麼其中一個是另一個的子集）。

我們現在考慮任意不是 \(t_0\) 的狀態 \(v\) 及後綴鏈接 \(\operatorname{link}(v)\)，由後綴鏈接和引理 2，我們可以得到

\[ \operatorname{endpos}(v)\subsetneq \operatorname{endpos}(\operatorname{link}(v)), \]

注意這裏應該是 \(\subsetneq\) 而不是 \(\subseteq\)，因為若 \(\operatorname{endpos}(v)=\operatorname{endpos}(\operatorname{link}(v))\)，那麼 \(v\) 和 \(\operatorname{link}(v)\) 應該被合併為一個節點

結合前面的引理有：後綴鏈接構成的樹本質上是 \(\operatorname{endpos}\) 集合構成的一棵樹。

以下是對字符串 \(\texttt{abcbc}\) 構造 SAM 時產生的後綴鏈接樹的一個例子，節點被標記為對應等價類中最長的子串。

小結

在學習算法本身前，我們總結一下之前學過的知識，並引入一些輔助記號。

\(s\) 的子串可以根據它們結束的位置 \(\operatorname{endpos}\) 被劃分為多個等價類；
SAM 由初始狀態 \(t_0\) 和與每一個 \(\operatorname{endpos}\) 等價類對應的每個狀態組成；
對於每一個狀態 \(v\)，一個或多個子串與之匹配。我們記 \(\operatorname{longest}(v)\) 為其中最長的一個字符串，記 \(\operatorname{len}(v)\) 為它的長度。類似地，記 \(\operatorname{shortest}(v)\) 為最短的子串，它的長度為 \(\operatorname{minlen}(v)\)。那麼對應這個狀態的所有字符串都是字符串 \(\operatorname{longest}(v)\) 的不同的後綴，且所有字符串的長度恰好覆蓋區間 \([\operatorname{minlen}(v),\operatorname{len}(v)]\) 中的每一個整數。
對於任意不是 \(t_0\) 的狀態 \(v\)，定義後綴鏈接為連接到對應字符串 \(\operatorname{longest}(v)\) 的長度為 \(\operatorname{minlen}(v)-1\) 的後綴的一條邊。從根節點 \(t_0\) 出發的後綴鏈接可以形成一棵樹。這棵樹也表示 \(\operatorname{endpos}\) 集合間的包含關係。
對於 \(t_0\) 以外的狀態 \(v\)，可用後綴鏈接 \(\operatorname{link}(v)\) 表達 \(\operatorname{minlen}(v)\)：

\[ \operatorname{minlen}(v)=\operatorname{len}(\operatorname{link}(v))+1. \]

如果我們從任意狀態 \(v_0\) 開始順着後綴鏈接遍歷，總會到達初始狀態 \(t_0\)。這種情況下我們可以得到一個互不相交的區間 \([\operatorname{minlen}(v_i),\operatorname{len}(v_i)]\) 的序列，且它們的並集形成了連續的區間 \([0,\operatorname{len}(v_0)]\)。

算法

現在我們可以學習構造 SAM 的算法了。這個算法是在線算法，我們可以逐個加入字符串中的每個字符，並且在每一步中對應地維護 SAM。

為了保證線性的空間複雜度，我們將只保存 \(\operatorname{len}\) 和 \(\operatorname{link}\) 的值和每個狀態的轉移列表，我們不會標記終止狀態（但是我們稍後會展示在構造 SAM 後如何分配這些標記）。

一開始 SAM 只包含一個狀態 \(t_0\)，編號為 \(0\)（其它狀態的編號為 \(1,2,\ldots\)）。為了方便，對於狀態 \(t_0\) 我們指定 \(\operatorname{len}=0\)、\(\operatorname{link}=-1\)（\(-1\) 表示虛擬狀態）。

過程

現在，任務轉化為實現給當前字符串添加一個字符 \(c\) 的過程。算法流程如下：

令 \(\textit{last}\) 為添加字符 \(c\) 之前，整個字符串對應的狀態（一開始我們設 \(\textit{last}=0\)，算法的最後一步更新 \(\textit{last}\)）。
創建一個新的狀態 \(\textit{cur}\)，並將 \(\operatorname{len}(\textit{cur})\) 賦值為 \(\operatorname{len}(\textit{last})+1\)，在這時 \(\operatorname{link}(\textit{cur})\) 的值還未知。
現在我們按以下流程進行（從狀態 \(\textit{last}\) 開始）。如果還沒有到字符 \(c\) 的轉移，我們就添加一個到狀態 \(\textit{cur}\) 的轉移，遍歷後綴鏈接。如果在某個點已經存在到字符 \(c\) 的轉移，我們就停下來，並將這個狀態標記為 \(p\)。
如果沒有找到這樣的狀態 \(p\)，我們就到達了虛擬狀態 \(-1\)，我們將 \(\operatorname{link}(\textit{cur})\) 賦值為 \(0\) 並退出。
假設現在我們找到了一個狀態 \(p\)，其可以通過字符 \(c\) 轉移。我們將轉移到的狀態標記為 \(q\)。
現在我們分類討論兩種狀態，要麼 \(\operatorname{len}(p) + 1 = \operatorname{len}(q)\)，要麼不是。
如果 \(\operatorname{len}(p)+1=\operatorname{len}(q)\)，我們只要將 \(\operatorname{link}(\textit{cur})\) 賦值為 \(q\) 並退出。
否則就會有些複雜。需要複製狀態 \(q\)：我們創建一個新的狀態 \(\textit{clone}\)，複製 \(q\) 的除了 \(\operatorname{len}\) 的值以外的所有信息（後綴鏈接和轉移）。我們將 \(\operatorname{len}(\textit{clone})\) 賦值為 \(\operatorname{len}(p)+1\)。
複製之後，我們將後綴鏈接從 \(\textit{cur}\) 指向 \(\textit{clone}\)，也從 \(q\) 指向 \(\textit{clone}\)。
最終我們需要使用後綴鏈接從狀態 \(p\) 往回走，只要存在一條通過 \(p\) 到狀態 \(q\) 的轉移，就將該轉移重定向到狀態 \(\textit{clone}\)。
以上三種情況，在完成這個過程之後，我們將 \(\textit{last}\) 的值更新為狀態 \(\textit{cur}\)。

如果我們還想知道哪些狀態是 終止狀態 而哪些不是，我們可以在為字符串 \(s\) 構造完完整的 SAM 後找到所有的終止狀態。為此，我們從對應整個字符串的狀態（存儲在變量 \(\textit{last}\) 中），遍歷它的後綴鏈接，直到到達初始狀態。我們將所有遍歷到的節點都標記為終止節點。容易理解這樣做我們會準確地標記字符串 \(s\) 的所有後綴，這些狀態都是終止狀態。

在下一部分，我們將詳細敍述算法每一步的細節，並證明它的 正確性。因為我們只為 \(s\) 的每個字符創建一個或兩個新狀態，所以 SAM 只包含 線性個 狀態。

而線性規模的轉移個數，以及算法總體的線性運行時間還不那麼清楚。

正確性證明

若一個轉移 \((p,q)\) 滿足 \(\operatorname{len}(p)+1=\operatorname{len}(q)\)，則我們稱這個轉移是 連續的。否則，即當 \(\operatorname{len}(p)+1<\operatorname{len}(q)\) 時，這個轉移被稱為 不連續的。從算法描述中可以看出，連續的、不連續的轉移是算法的不同情況。連續的轉移是固定的，我們不會再改變了。與此相反，當向字符串中插入一個新的字符時，不連續的轉移可能會改變（轉移邊的端點可能會改變）。
為了避免引起歧義，我們記向 SAM 中插入當前字符 \(c\) 之前的字符串為 \(s\)。
算法從創建一個新狀態 \(\textit{cur}\) 開始，對應於整個字符串 \(s+c\)。我們創建一個新的節點的原因很清楚。與此同時我們也創建了一個新的字符和一個新的等價類。
在創建一個新的狀態之後，我們會從對應整個字符串 \(s\) 的狀態通過後綴鏈接進行遍歷。對於每一個狀態，我們嘗試添加一個通過字符 \(c\) 到新狀態 \(\textit{cur}\) 的轉移。然而我們只能添加與原有轉移不衝突的轉移。因此我們只要找到已存在的 \(c\) 的轉移，我們就必須停止。
最簡單的情況是我們到達了虛擬狀態 \(-1\)，這意味着我們為所有 \(s\) 的後綴添加了 \(c\) 的轉移。這也意味着，字符 \(c\) 從未在字符串 \(s\) 中出現過。因此 \(\textit{cur}\) 的後綴鏈接為狀態 \(0\)。
第二種情況下，我們找到了現有的轉移 \((p,q)\)。這意味着我們嘗試向自動機內添加一個 已經存在的 字符串 \(x+c\)（其中 \(x\) 為 \(s\) 的一個後綴，且字符串 \(x+c\) 已經作為 \(s\) 的一個子串出現過了）。因為我們假設字符串 \(s\) 的自動機的構造是正確的，我們不應該在這裏添加一個新的轉移。然而，難點在於，從狀態 \(\textit{cur}\) 出發的後綴鏈接應該連接到哪個狀態呢？我們要把後綴鏈接連到一個狀態上，且其中最長的一個字符串恰好是 \(x+c\)，即這個狀態的 \(\operatorname{len}\) 應該是 \(\operatorname{len}(p)+1\)。然而還不存在這樣的狀態，即 \(\operatorname{len}(q)>\operatorname{len}(p)+1\)。這種情況下，我們必須通過拆開狀態 \(q\) 來創建一個這樣的狀態。
如果轉移 \((p,\,q)\) 是連續的，那麼 \(\operatorname{len}(q)=\operatorname{len}(p)+1\)。在這種情況下一切都很簡單。我們只需要將 \(\textit{cur}\) 的後綴鏈接指向狀態 \(q\)。
否則轉移是不連續的，即 \(\operatorname{len}(q)>\operatorname{len}(p)+1\)，這意味着狀態 \(q\) 不只對應於長度為 \(\operatorname{len}(p)+1\) 的後綴 \(s+c\)，還對應於 \(s\) 的更長的子串。除了將狀態 \(q\) 拆成兩個子狀態以外我們別無他法，所以第一個子狀態的長度就是 \(\operatorname{len}(p)+1\) 了。
我們如何拆開一個狀態呢？我們複製狀態 \(q\)，產生一個狀態 \(\textit{clone}\)，我們將 \(\operatorname{len}(\textit{clone})\) 賦值為 \(\operatorname{len}(p)+1\)。由於我們不想改變遍歷到 \(q\) 的路徑，我們將 \(q\) 的所有轉移複製到 \(\textit{clone}\)。我們也將從 \(\textit{clone}\) 出發的後綴鏈接設置為 \(q\) 的後綴鏈接的目標，並設置 \(q\) 的後綴鏈接為 \(\textit{clone}\)。
在拆開狀態後，我們將從 \(\textit{cur}\) 出發的後綴鏈接設置為 \(\textit{clone}\)。
最後一步我們將一些到 \(q\) 轉移重定向到 \(\textit{clone}\)。我們需要修改哪些轉移呢？只重定向相當於所有字符串 \(w+c\)（其中 \(w\) 是 \(p\) 的最長字符串）的後綴就夠了。即，我們需要繼續沿着後綴鏈接遍歷，從結點 \(p\) 直到虛擬狀態 \(-1\) 或者是轉移到不是狀態 \(q\) 的一個轉移。

對操作次數為線性的證明

所以我們將認為字符集的大小為常數，即每次對一個字符搜索轉移、添加轉移、查找下一個轉移。這些操作的時間複雜度都為 \(O(1)\)。

如果我們考慮算法的各個部分，算法中有三處時間複雜度不明顯是線性的：

第一處是遍歷所有狀態 \(\textit{last}\) 的後綴鏈接，添加字符 \(c\) 的轉移。
第二處是當狀態 \(q\) 被複制到一個新的狀態 \(\textit{clone}\) 時複製轉移的過程。
第三處是修改指向 \(q\) 的轉移，將它們重定向到 \(\textit{clone}\) 的過程。

我們使用 SAM 的大小（狀態數和轉移數）為 線性的 的事實（對狀態數是線性的的證明就是算法本身，對轉移數為線性的的證明將在稍後實現算法後給出）。

因此上述 第一處和第二處 的總複雜度顯然為線性的，因為單次操作均攤只為自動機添加了一個新轉移。

還需為 第三處 估計總複雜度，我們將最初指向 \(q\) 的轉移重定向到 \(\textit{clone}\)。我們記 \(v=\operatorname{longest}(p)\)，這是一個字符串 \(s\) 的後綴，每次迭代長度都遞減——因為字符串 \(s\) 的位置每次迭代都單調上升。這種情況下，如果在循環的第一次迭代之前，相對應的字符串 \(v\) 在距離 \(\textit{last}\) 的深度為 \(k\) \((k\ge 2)\) 的位置上（深度記為後綴鏈接的數量），那麼在最後一次迭代後，字符串 \(v+c\) 將會成為路徑上第二個從 \(\textit{cur}\) 出發的後綴鏈接（它將會成為新的 \(\textit{last}\) 的值）。

因此，循環中的每次迭代都會使作為當前字符串的後綴的字符串 \(\operatorname{longest}(\operatorname{link}(\operatorname{link}(\textit{last}))\) 的位置單調遞增。因此這個循環最多不會執行超過 \(n\) 次迭代，這正是我們需要證明的。

實現

首先，我們實現一種存儲一個轉移的全部信息的數據結構。如果需要的話，你可以在這裏加入一個終止標記，也可以是一些其它信息。我們將用一個 map 存儲轉移的列表，允許我們在總計 \(O(n)\) 的空間複雜度和 \(O(n\log\left|\Sigma\right|)\) 的時間複雜度內處理整個字符串。（注：在字符集大小為較小的常數，比如 26 時，將 next 定義為 int[26] 更方便）

struct state {
  int len, link;
  std::map<char, int> next;
};

SAM 本身將會存儲在一個 state 結構體數組中。我們記錄當前自動機的大小 sz 和變量 last，當前整個字符串對應的狀態。

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

我們定義一個函數來初始化 SAM（創建一個只有初始狀態的 SAM）。

void sam_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz++;
  last = 0;
}

最終我們給出主函數的實現：給當前行末增加一個字符，對應地在之前的基礎上建造自動機。

實現

void sam_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

應用

下面我們來看一些可以用 SAM 解決的問題。簡單起見，假設字符集的大小 \(k\) 為常數。這允許我們認為增加一個字符和遍歷的複雜度為常數。

檢查字符串是否出現

給一個文本串 \(T\) 和多個模式串 \(P\)，我們要檢查字符串 \(P\) 是否作為 \(T\) 的一個子串出現。

我們在 \(O(\left|T\right|)\) 的時間內對文本串 \(T\) 構造後綴自動機。為了檢查模式串 \(P\) 是否在 \(T\) 中出現，我們沿轉移（邊）從 \(t_0\) 開始根據 \(P\) 的字符進行轉移。如果在某個點無法轉移下去，則模式串 \(P\) 不是 \(T\) 的一個子串。如果我們能夠這樣處理完整個字符串 \(P\)，那麼模式串在 \(T\) 中出現過。

對於每個字符串 \(P\)，算法的時間複雜度為 \(O(\left|P\right|)\)。此外，這個算法還找到了模式串 \(P\) 在文本串中出現的最大前綴長度。

不同子串個數

給一個字符串 \(S\)，計算不同子串的個數。

對字符串 \(S\) 構造後綴自動機。

每個 \(S\) 的子串都相當於自動機中的一些路徑。因此不同子串的個數等於自動機中以 \(t_0\) 為起點的不同路徑的條數。

考慮到 SAM 為有向無環圖，不同路徑的條數可以通過動態規劃計算。即令 \(d_{v}\) 為從狀態 \(v\) 開始的路徑數量（包括長度為零的路徑），則我們有如下遞推方程：

\[ d_{v}=1+\sum_{w:(v,w,c)\in DAWG}d_{w} \]

即，\(d_{v}\) 可以表示為所有 \(v\) 的轉移的末端的和。

所以不同子串的個數為 \(d_{t_0}-1\)（因為要去掉空子串）。

總時間複雜度為：\(O(\left|S\right|)\)。

另一種方法是利用上述後綴自動機的樹形結構。每個節點對應的子串數量是 \(\operatorname{len}(i)-\operatorname{len}(\operatorname{link}(i))\)，對自動機所有節點求和即可。

例題：【模板】後綴自動機，SDOI2016 生成魔咒

所有不同子串的總長度

給定一個字符串 \(S\)，計算所有不同子串的總長度。

本題做法與上一題類似，只是現在我們需要考慮分兩部分進行動態規劃：不同子串的數量 \(d_{v}\) 和它們的總長度 \(ans_{v}\)。

我們已經在上一題中介紹瞭如何計算 \(d_{v}\)。\(ans_{v}\) 的值可以通過以下遞推式計算：

\[ ans_{v}=\sum_{w:(v,w,c)\in DAWG}d_{w}+ans_{w} \]

我們取每個鄰接結點 \(w\) 的答案，並加上 \(d_{w}\)（因為從狀態 \(v\) 出發的子串都增加了一個字符）。

算法的時間複雜度仍然是 \(O(\left|S\right|)\)。

同樣可以利用上述後綴自動機的樹形結構。每個節點對應的所有後綴長度是 \(\frac{\operatorname{len}(i)\times (\operatorname{len}(i)+1)}{2}\)，減去其 \(\operatorname{link}\) 節點的對應值就是該節點的淨貢獻，對自動機所有節點求和即可。

字典序第 k 大子串

給定一個字符串 \(S\)。多組詢問，每組詢問給定一個數 \(K_i\)，查詢 \(S\) 的所有子串中字典序第 \(K_i\) 大的子串。

解決這個問題的思路可以從解決前兩個問題的思路發展而來。字典序第 \(k\) 大的子串對應於 SAM 中字典序第 \(k\) 大的路徑，因此在計算每個狀態的路徑數後，我們可以很容易地從 SAM 的根開始找到第 \(k\) 大的路徑。

雖然該題是後綴自動機的經典題，但實際上這題由於涉及字典序，用後綴數組做最方便。

例題：SPOJ - SUBLEX，TJOI2015 弦論

最小循環移位

給定一個字符串 \(S\)。找出字典序最小的循環移位。

容易發現字符串 \(S+S\) 包含字符串 \(S\) 的所有循環移位作為子串。

所以問題簡化為在 \(S+S\) 對應的後綴自動機上尋找最小的長度為 \(\left|S\right|\) 的路徑，這可以通過平凡的方法做到：我們從初始狀態開始，貪心地訪問最小的字符即可。

總的時間複雜度為 \(O(\left|S\right|)\)。

出現次數

對於一個給定的文本串 \(T\)，有多組詢問，每組詢問給一個模式串 \(P\)，回答模式串 \(P\) 在字符串 \(T\) 中作為子串出現了多少次。

利用後綴自動機的樹形結構，進行 dfs 即可預處理每個節點的終點集合大小。在自動機上查找模式串 \(P\) 對應的節點，如果存在，則答案就是該節點的終點集合大小；如果不存在，則答案為 \(0\).

以下為原方法：

對文本串 \(T\) 構造後綴自動機。

接下來做預處理：對於自動機中的每個狀態 \(v\)，預處理 \(cnt_{v}\)，使之等於 \(\operatorname{endpos}(v)\) 集合的大小。事實上，對應同一狀態 \(v\) 的所有子串在文本串 \(T\) 中的出現次數相同，這相當於集合 \(\operatorname{endpos}\) 中的位置數。

然而我們不能明確的構造集合 \(\operatorname{endpos}\)，因此我們只考慮它們的大小 \(cnt\)。

為了計算這些值，我們進行以下操作。對於每個狀態，如果它不是通過複製創建的（且它不是初始狀態 \(t_0\)），我們將它的 \(cnt\) 初始化為 1。然後我們按它們的長度 \(\operatorname{len}\) 降序遍歷所有狀態，並將當前的 \(cnt_{v}\) 的值加到後綴鏈接指向的狀態上，即：

\[ cnt_{\operatorname{link}(v)}+=cnt_{v} \]

這樣做每個狀態的答案都是正確的。

為什麼這是正確的？不是通過複製獲得的狀態，恰好有 \(\left|T\right|\) 個，並且它們中的前 \(i\) 個在我們插入前 \(i\) 個字符時產生。因此對於每個這樣的狀態，我們在它被處理時計算它們所對應的位置的數量。因此我們初始將這些狀態的 \(cnt\) 的值賦為 \(1\)，其它狀態的 \(cnt\) 值賦為 \(0\)。

接下來我們對每一個 \(v\) 執行以下操作：\(cnt_{\operatorname{link}(v)}+=cnt_{v}\)。其背後的含義是，如果有一個字符串 \(v\) 出現了 \(cnt_{v}\) 次，那麼它的所有後綴也在完全相同的地方結束，即也出現了 \(cnt_{v}\) 次。

為什麼我們在這個過程中不會重複計數（即把某些位置數了兩次）呢？因為我們只將一個狀態的位置添加到一個其它的狀態上，所以一個狀態不可能以兩種不同的方式將其位置重複地指向另一個狀態。

因此，我們可以在 \(O(\left|T\right|)\) 的時間內計算出所有狀態的 \(cnt\) 的值。

最後回答詢問只需要查找值 \(cnt_{t}\)，其中 \(t\) 為模式串對應的狀態，如果該模式串不存在答案就為 \(0\)。單次查詢的時間複雜度為 \(O(\left|P\right|)\)。

第一次出現的位置

給定一個文本串 \(T\)，多組查詢。每次查詢字符串 \(P\) 在字符串 \(T\) 中第一次出現的位置（\(P\) 的開頭位置）。

我們構造一個後綴自動機。我們對 SAM 中的所有狀態預處理位置 \(\operatorname{firstpos}\)。即，對每個狀態 \(v\) 我們想要找到第一次出現這個狀態的末端的位置 \(\operatorname{firstpos}[v]\)。換句話説，我們希望先找到每個集合 \(\operatorname{endpos}\) 中的最小的元素（顯然我們不能顯式地維護所有 \(\operatorname{endpos}\) 集合）。

為了維護 \(\operatorname{firstpos}\) 這些位置，我們將原函數擴展為 sam_extend()。當我們創建新狀態 \(\textit{cur}\) 時，我們令：

\[ \operatorname{firstpos}(\textit{cur})=\operatorname{len}(\textit{cur})-1 \]

；當我們將結點 \(q\) 複製到 \(\textit{clone}\) 時，我們令：

\[ \operatorname{firstpos}(\textit{clone})=\operatorname{firstpos}(q) \]

（因為值的唯一的其它選項 \(\operatorname{firstpos}(\textit{cur})\) 顯然太大了）。

那麼查詢的答案就是 \(\operatorname{firstpos}(t)-\left|P\right|+1\)，其中 \(t\) 為對應字符串 \(P\) 的狀態。單次查詢只需要 \(O(\left|P\right|)\) 的時間。

所有出現的位置

問題同上，這一次需要查詢文本串 \(T\) 中模式串出現的所有位置。

利用後綴自動機的樹形結構，遍歷子樹，一旦發現終點節點就輸出。

以下為原解法：

我們還是對文本串 \(T\) 構造後綴自動機。與上一個問題相似，我們為所有狀態計算位置 \(\operatorname{firstpos}\)。

如果 \(t\) 為對應於模式串 \(T\) 的狀態，顯然 \(\operatorname{firstpos}(t)\) 為答案的一部分。需要查找的其它位置怎麼辦？我們使用了含有字符串 \(P\) 的自動機，我們還需要將哪些狀態納入自動機呢？所有對應於以 \(P\) 為後綴的字符串的狀態。換句話説我們要找到所有可以通過後綴鏈接到達狀態 \(t\) 的狀態。

因此為了解決這個問題，我們需要為每一個狀態保存一個指向它的後綴引用列表。查詢的答案就包含了對於每個我們能從狀態 \(t\) 只使用後綴引用進行 DFS 或 BFS 的所有狀態的 \(\operatorname{firstpos}\) 值。

這種變通方案的時間複雜度為 \(O(\textit{answer}(P))\)，因為我們不會重複訪問一個狀態（因為對於僅有一個後綴鏈接指向一個狀態，所以不存在兩條不同的路徑指向同一狀態）。

我們只需要考慮兩個可能有相同 \(\operatorname{endpos}\) 值的不同狀態。如果一個狀態是由另一個複製而來的，則這種情況會發生。然而，這並不會對複雜度分析造成影響，因為每個狀態至多被複制一次。

此外，如果我們不從被複制的節點輸出位置，我們也可以去除重複的位置。事實上對於一個狀態，如果經過被複制狀態可以到達，則經過原狀態也可以到達。因此，如果我們給每個狀態記錄標記 is_clone 來代表這個狀態是不是被複製出來的，我們就可以簡單地忽略掉被複制的狀態，只輸出其它所有狀態的 \(firstpos\) 的值。

以下是大致的實現：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct state {
  bool is_clone;
  int first_pos;
  std::vector<int> inv_link;
  // some other variables
};

// 在構造 SAM 後
for (int v = 1; v < sz; v++) st[st[v].link].inv_link.push_back(v);

// 輸出所有出現位置
void output_all_occurrences(int v, int P_length) {
  if (!st[v].is_clone) cout << st[v].first_pos - P_length + 1 << endl;
  for (int u : st[v].inv_link) output_all_occurrences(u, P_length);
}

最短的沒有出現的字符串

給定一個字符串 \(S\) 和一個特定的字符集，我們要找一個長度最短的沒有在 \(S\) 中出現過的字符串。

我們在字符串 \(S\) 的後綴自動機上做動態規劃。

令 \(d_{v}\) 為節點 \(v\) 的答案，即，我們已經處理完了子串的一部分，當前在狀態 \(v\)，想找到不連續的轉移需要添加的最小字符數量。計算 \(d_{v}\) 非常簡單。如果不存在使用字符集中至少一個字符的轉移，則 \(d_{v}=1\)。否則添加一個字符是不夠的，我們需要求出所有轉移中的最小值：

\[ d_{v}=1+\min_{w:(v,w,c)\in SAM}d_{w} \]

問題的答案就是 \(d_{t_0}\)，字符串可以通過計算過的數組 \(d\) 逆推回去。

兩個字符串的最長公共子串

給定兩個字符串 \(S\) 和 \(T\)，求出最長公共子串，公共子串定義為在 \(S\) 和 \(T\) 中都作為子串出現過的字符串 \(X\)。

我們對字符串 \(S\) 構造後綴自動機。

我們現在處理字符串 \(T\)，對於每一個前綴，都在 \(S\) 中尋找這個前綴的最長後綴。換句話説，對於每個字符串 \(T\) 中的位置，我們想要找到這個位置結束的 \(S\) 和 \(T\) 的最長公共子串的長度。顯然問題的答案就是所有 \(l\) 的最大值。

為了達到這一目的，我們使用兩個變量，當前狀態 \(v\) 和 當前長度 \(l\)。這兩個變量描述當前匹配的部分：它的長度和它們對應的狀態。

一開始 \(v=t_0\) 且 \(l=0\)，即，匹配為空串。

現在我們來描述如何添加一個字符 \(T_{i}\) 併為其重新計算答案：

如果存在一個從 \(v\) 到字符 \(T_{i}\) 的轉移，我們只需要轉移並讓 \(l\) 自增一。
如果不存在這樣的轉移，我們需要縮短當前匹配的部分，這意味着我們需要按照後綴鏈接進行轉移：

\[ v=\operatorname{link}(v) \]

與此同時，需要縮短當前長度。顯然我們需要將 \(l\) 賦值為 \(\operatorname{len}(v)\)，因為經過這個後綴鏈接後我們到達的狀態所對應的最長字符串是一個子串。

如果仍然沒有使用這一字符的轉移，我們繼續重複經過後綴鏈接並減小 \(l\)，直到我們找到一個轉移或到達虛擬狀態 \(-1\)（這意味着字符 \(T_{i}\) 根本沒有在 \(S\) 中出現過，所以我們設置 \(v=l=0\)）。

這一部分的時間複雜度為 \(O(\left|T\right|)\)，因為每次移動我們要麼可以使 \(l\) 增加一，要麼可以在後綴鏈接間移動幾次，每次都減小 \(l\) 的值。

代碼實現：

string lcs(const string &S, const string &T) {
  sam_init();
  for (int i = 0; i < S.size(); i++) sam_extend(S[i]);

  int v = 0, l = 0, best = 0, bestpos = 0;
  for (int i = 0; i < T.size(); i++) {
    while (v && !st[v].next.count(T[i])) {
      v = st[v].link;
      l = st[v].length;
    }
    if (st[v].next.count(T[i])) {
      v = st[v].next[T[i]];
      l++;
    }
    if (l > best) {
      best = l;
      bestpos = i;
    }
  }
  return T.substr(bestpos - best + 1, best);
}

例題：SPOJ Longest Common Substring

多個字符串間的最長公共子串

給定 \(k\) 個字符串 \(S_i\)。我們需要找到它們的最長公共子串，即作為子串出現在每個字符串中的字符串 \(X\)。

我們將所有的子串連接成一個較長的字符串 \(T\)，以特殊字符 \(D_i\) 分開每個字符串（一個字符對應一個字符串）：

\[ T=S_1+D_1+S_2+D_2+\cdots+S_k+D_k. \]

然後對字符串 \(T\) 構造後綴自動機。

現在我們需要在自動機中找到存在於所有字符串 \(S_i\) 中的一個字符串，這可以通過使用添加的特殊字符完成。注意如果 \(S_j\) 包含了一個子串，則 SAM 中存在一條從包含字符 \(D_j\) 的子串而不包含以其它字符 \(D_1,\,\ldots,\,D_{j-1},\,D_{j+1},\,\ldots,\,D_k\) 開始的路徑。

因此我們需要計算可達性，即對於自動機中的每個狀態和每個字符 \(D_i\)，是否存在這樣的一條路徑。這可以容易地通過 DFS 或 BFS 及動態規劃計算。之後，問題的答案就是狀態 \(v\) 的字符串 \(\operatorname{longest}(v)\) 中存在所有特殊字符的路徑。

例題：SPOJ Longest Common Substring II

後綴自動機 (SAM)

一些前置約定/定義

後綴自動機概述

定義

子串的性質

構建過程

在線性時間內構造

結束位置 `endpos`

後綴鏈接 `link`

小結

算法

過程

正確性證明

對操作次數為線性的證明

實現

更多性質

狀態數

轉移數

額外信息

應用

檢查字符串是否出現

不同子串個數

所有不同子串的總長度

字典序第 k 大子串

最小循環移位

出現次數

第一次出現的位置

所有出現的位置

最短的沒有出現的字符串

兩個字符串的最長公共子串

多個字符串間的最長公共子串

例題

相關資料

後綴自動機 (SAM)

一些前置約定/定義

後綴自動機概述

定義

子串的性質

構建過程

在線性時間內構造

結束位置 endpos

後綴鏈接 link

小結

算法

過程

正確性證明

對操作次數為線性的證明

實現

更多性質

狀態數

轉移數

額外信息

應用

檢查字符串是否出現

不同子串個數

所有不同子串的總長度

字典序第 k 大子串

最小循環移位

出現次數

第一次出現的位置

所有出現的位置

最短的沒有出現的字符串

兩個字符串的最長公共子串

多個字符串間的最長公共子串

例題

相關資料

結束位置 `endpos`

後綴鏈接 `link`