0.前言

這種東西不知道是怎么發明出來了的。感覺很 nb。

但是應該比 KMP 簡單些吧。

oi-wiki

1.概念

SAM，即后綴自動機，是對于一個字符串 \(s\) 來說能夠表示其所有子串/后綴的 DFA。實際上 SAM 是一個 DAG，上面有若干點代表若干狀態，其中有一個初始狀態 \(t_0\)，這些狀態所代表的字符串可能不止一個，SAM 上的邊代表若干轉移，每個轉移是一個字母，從一個狀態連接到另一個狀態。SAM 上的每條從 \(t_0\) 作為起始點的路徑上的所有轉移所組成的字符串實際上是原字符串 \(s\) 的某個子串，這個子串屬于這條路徑的終點的狀態所代表的字符串集合。

2.神秘性質

right 集合

首先我們定義：對于字符串 \(s\) 的一個非空子串 \(s_0\)，其 right 集合為 \(s_0\) 在 \(s\) 中出現的所有結束位置。

顯然，可以得到如下性質：

1. SAM 上的一個狀態對應著若干 right 集合相同的子串，如果將這些子串按長度從小到大排序之后，它們的長度連續。

2. \( \begin{cases} right(x) \subseteq right(y) & \text{if y is a suffix of x.}\\ right(x) \cap right(y) = \phi & \text{otherwise.} \end{cases} \)

3. 如果子串 \(x\) 與 \(y\) 的 right 集合相同，那么較短的那個一定是較長的后綴。

后綴鏈接 fa

根據 right 集合的性質，我們可以根據 SAM 的 DAG 構建 Parent Tree。

對于狀態 \(X\)，其后綴鏈接就是連接到 right 集合不同的最長后綴所屬狀態 \(Y\) 上。

令 \(t\) 為狀態 \(X\) 中最長的字符串，現在我們知道字符串 \(t\) 的前若干個后綴的 right 集合與 \(t\) 相同，而后若干個后綴的 right 集合不與 \(t\) 相同，令滿足后者的最長后綴為 \(v\)，則 \(right(t) \subseteq right(v)\)。
這就相當于不斷地在 \(t\) 的開頭刪除字母，所得到的字符串長度會越來越短，當刪到某一個后綴 \(v\) 時，發現其不僅在 \(t\) 出現的這些地方出現過，還在原串 \(s\) 的其他地方出現過。所以其 right 集合會變大，且包含 \(right(t)\) 中的元素。
那么 \(X\) 的后綴鏈接會連接到 \(v\) 所在狀態 \(Y\) 上。

• 所有的后綴鏈接會構成一棵以 \(t_0\) 為根節點的樹。

• 通過 right 集合構造的樹（每個子節點的 right 集合都包含在父節點的 right 集合中）與通過后綴鏈接構造的樹相同。

• 在維護 SAM 的時候，通常會記錄狀態所代表子串的最大長度 \(len_u\)，可以發現，在 Parent Tree 上，一個狀態代表子串的長度范圍應為 \([len_{fa_u} + 1,len_u]\)。

上述性質是顯然的。我們建出來的自動機實際上是 DAG + Parent Tree。

3.構造 SAM

令一個狀態 \(u\) 代表子串中最長子串為 \(longest(u)\)。

當前字符串為 \(s\)，新加入的字符為 \(c\)，新添加的狀態為 \(u\)。構造過程如下：

從上一次 \(s\) 的狀態 \(p\) 開始向上跳后綴鏈接，直到 \(p\) 在 DAG 上有一條為 \(c\) 的轉移；
如果沒有找到，那么我們添加的就是一個新字母，\(fa_u = t_0\) 即可。如果找到了，令這個轉移到的狀態為 \(q\)：

1. 如果 \(len_q = len_p + 1\)，證明 \(q\) 只代表 \(longest(p) + c\) 這一個子串，直接將 \(u\) 的后綴鏈接到 \(q\)；
2. 如果 \(len_q > len_p + 1\)，證明 \(q\) 不止代表 \(longest(p) + c\) 這一個子串，這時我們需要將 \(q\) 拆開，拆為一個只代表 \(longest(p) + c\) 這一個子串的狀態 \(now\) 和剩余部分 \(q'\)，將 \(now\) 的后綴鏈接連接到 \(p\)，并將 \(q'\) 與 \(u\) 的后綴鏈接連接到 \(now\)，接著，我們繼續用 \(p\) 通過后綴鏈接向上跳，如果存在狀態有為 \(c\) 的轉移是指向原本的 \(q\) 的，將其指向 \(now\)。

這么做是因為我們從 \(s\) 所屬狀態開始跳后綴鏈接，而達到的點均為 \(s\) 的后綴，當這些后綴中存在為 \(c\) 的轉移時，這個轉移所到達的狀態一定是 \(s + c\) 的一個后綴且是最長的 right 集合與 \(right(u)\) 不同的后綴。

SAM 便構造完畢。

4.不錯的應用

oi-wiki 已經足夠詳細。