字符串
\(\text{Aho-Corasick Automaton}\)
前言：
- \(\text{maton}\to \text{mata}(pl.)\)
- \(\text{matrix}\to\text{matrices}(pl.)\)
- 確定性有限自動機（\(\text{Deterministic Finite Automaton}\)）
- 非確定性有限自動機（\(\text{NonDeterministic Finite Automaton}\)）
流程
總述：因為一個字符串的字串是它的一個前綴的后綴，所以我們開一個字典樹維護前綴，再在字典樹上開一個失配樹維護后綴。
我們知道，KMP 自動機僅限單個字符串，那么對于多個字符串就需要 AC 自動機了，就像廣義后綴自動機對于后綴自動機一樣。下圖是一張已經建好的圖。
具體地，首先要建一棵 Trie。綠邊便是 Trie 本來的邊，而黃邊是 fail 指針。fail 指針也叫失配指針，類似于 KMP 當中的 next 指針。注意到 fail 指針的含義就是連向它的最長后綴。
如何構建 fail 指針？首先我們應該知道，應該按照 bfs 的方式去處理，因為只有當深層較小的 fail 指針都處理完后，才能更新深度較大的 fail 指針。
結合 KMP 的思想（下文用 \(f\) 表示 fail 指針，\(t\) 表示字典樹上的邊），假設當前是狀態 \(u\) 推 \(v=t[u][c]\)，那么如果 \(t[f[u]][c]\) 存在，那么 \(v\) 的 fail 指針便可以繼承為 \(t[f[u]][c]\)；否則，根據定義，若 \(k=f[u]\)，不斷令 \(k=f[k]\)，直到 \(t[k][c]\) 存在或者報告沒有。
這種求 fail 指針的方法時間復雜度很玄學，是 \(c\sum|s|?\)，因為既無法給出卡掉的例子，也無法證明時間復雜度，所以只需理解即可。這種 AC 自動機是 NFA。
Trie 圖
引出一種新概念。在 Trie 上，\(t[u][c]\) 僅表示一條真實存在的邊，現在進行延伸，表示通過字符 \(c\) 到達的狀態。
于是在 bfs 的基礎上，一邊求出 fail 指針，一邊建立 Trie 圖。那么 \(f[t[u][c]]\) 直接為 \(t[f[u]][c]\)，這是當 \(t[u][c]\) 存在的情況；否則 \(t[u][c]=t[f[u]][c]\)。
這樣時間復雜度便是確定的 \(O(c\sum|s|)\)。Trie 圖在很多題中都需要用到。
性質
由于 fail 指針由深連向淺，所以一定構成一棵樹。既然是樹，那么便有很多可發揮的空間。如，高斯消元求解樹上隨機游走、dfs 序建可持久化線段樹等。
但是最常見的還是 dp。如果要求把一個字符串分成若干段，如果一段是給定字符串，那么就加上一個貢獻；最后問最大貢獻。這就是一個 AC 自動機上 dp 經典例題。如果每次暴力去跳 fail 的話，顯然會超時，但是注意到跳的時候有很多無效狀態（即不是某個串的末尾），這時候就要縮鏈，即確保每次跳都是有效的。可以證明這樣復雜度極限是 \(O(n\sqrt n)\)。
當然，如果轉移只跟當前狀態有關，也可以建好圖后直接求解。
\(\text{Palindromic Tree}\)
又稱回文自動機（PAM）。
一個狀態 \(u\) 表示一個回文子串 \(t_u\)，\(to[u][c]\) 表示在 \(t_u\) 兩邊加上 \(c\) 到達的狀態，\(f[u]\) 既然是失配指針，則表示 \(t_u\) 的最長回文后綴?？紤]怎么建出這個回文自動機。
流程
先建兩個初始點 \(s0\) 和 \(s1\)，可以理解為 \(s0\) 長度為 \(0\)，\(s1\) 長度為 \(-1\)，那么 \(f[s0]=s1\)。記 \(p\) 為當前狀態，\(l[u]\) 為 \(t_u\) 的長度。
令 \(q=p\)，對于字符 \(s_i\)，不斷讓 \(q\) 跳 fail 直到 \(s_i=s_{i-l[q]-1}\)，如果 \(v=to[q][s_i]\) 不存在則增加狀態，該狀態即為以 \(s_i\) 結尾的最長回文子串。顯然 \(l[v]=l[q]+2\)。考慮求出 fail 指針，從 \(q\) 再往上跳，判定條件不變，找到 \(t_v\) 的最長回文子串，\(f[v]=to[q][s_i]\)。然后將 \(p\) 設為 \(v\)。
分析一下時間復雜度，分析 \(l\) 的變化情況，每次往上跳 \(l\to l-2\)，找到后最終 \(l\to l+2\)，容易發現全局最多跳 \(O(n)\) 次，所以是對的。以下是 abaa 的回文自動機。
性質
通過回文自動機的流程可以證明一個字符串本質不同的回文子串個數嚴格不超過 \(n\)，因為每次最多新增一個狀態，而狀態不會漏（因為更小的回文子串前面一定出現過）。
和 AC 自動機類似的，一些問題也可以轉到 fail 樹上求解。
\(\text{Suffix Array}\)
可以求出把一個字符串的所有后綴按字典序排序后，以 \(i\) 開始的后綴的排名 \(rk_i\) 以及排名為 \(i\) 的后綴的起始位置 \(sa_i\)。以下欽定字符串下標從 \(1\) 開始，長度為 \(n\)，\(s_i\) 表示 \(i\) 開頭的后綴。
倍增法
規定 \(s_{n+1\sim 2n}\) 為負無窮，\(rk_{i,j}\) 表示 \(i\sim i+2^{j}-1\) 這段區間在長度為 \(2^j\) 當中的排名，\(sa_{i,j}\) 同理。
考慮利用倍增思想，在比較 \(rk_{i,j}\) 與 \(rk_{k,j}\) 的時候，本質上是先比較 \(rk_{i,j-1}\) 與 \(rk_{k,j-1}\)，然后再比較 \(rk_{i+2^{j-1},j-1}\) 與 \(rk_{k+2^{j-1},j-1}\)，于是執行 \(\log n\) 次雙關鍵字排序便可做到 \(O(n\log^2 n)\)?？紤]優化。
事實上 \(rk\) 的值域很小，所以可以考慮基數排序，先以第二關鍵字進行計數排序，再以第一關鍵字進行計數排序。這樣時間復雜度是 \(O(n\log n)\)，但是常數很大。發現在以第二關鍵字進行排序時不需要進行計數排序，事實上等價于將 \(i>n-2^{j-1}\) 放到開頭，其余按順序即可，感性理解。
當然有 \(O(n)\) 的方法，但是并不常用。
容易發現 \(rk_{sa_i}=sa_{rk_i}=i\)。
height 數組
非常有用的東西，以下簡寫為 \(h\)。
\(h_i=\text{lcp}(s_{sa_{i-1}},s_{sa_i})\)，即排序后相鄰兩個后綴的最長公共前綴，求的話可以二分加哈希做到 \(O(n\log n)\)?？紤]優化。
定理：\(h_{rk_i}\ge h_{rk_{i-1}}-1\)。
考慮證明，不妨假設 \(s_{i-1}=aAD\)，那么 \(s_i=AD\)。假如 \(aA\) 的長度為 \(h_{rk_{i-1}}\)，那么 \(s_{sa_{rk_{i-1}-1}}=aAB\)，并且有 \(B<D\)。于是顯然存在一個后綴 \(s_j\) 為 \(AB\)，那么有 \(AB\le s_{sa_{rk_{i}-1}}<AD\)，證畢。
于是便可以直接 \(O(n)\) 求出 \(h\) 了。
性質
- 如果 \(i<j\)，則 \(\text{lcp}(s_{sa_i},s_{sa_j})=\min\limits_{k=i+1}^{j}h_k\)。感性理解即可。于是求任意兩個后綴的 \(\text{lcp}\) 便能用 st 表做到 \(O(1)\)。
- \(S\) 本質不同的子串個數為 \(\frac{n(n+1)}{2}-\sum\limits_{i=1}^{n}h_i\)。
- 求第 \(k\) 大子串可以通過二分的方式，找到第一個 \(g_i=\sum\limits_{i=1}^{x}l_i-h_i\ge k\) 的位置，\(l_i\) 表示 \(s_{sa_i}\) 的長度，答案就是 \(s_{sa_i,sa_i+k-g_{i-1}}\)。
\(\text{Suffix AutoMaton}\)
下圖分別是 abcbc 的 to 和 fail。
。
狀態及 \(\text{endpos}\)
一個狀態表示一個等價類，等價類是一個子串集合，里面所有字符串的 \(\text{endpose}\) 集合相同。對于子串 \(t\)，\(\text{endpose}(t)\) 為 \(t\) 在原串 \(s\) 中所有結束位置的集合。
定理一：假設 \(|t1|>|t2|\)，則 \(\text{endpos}(t1)=\text{endpos}(t2)\) 為 \(t2\in S(t1)\) 的充分條件，其中 \(S(t)\) 表示 \(t\) 的后綴集合。
推論一：假設 \(|t1|>|t2|\)，則要么 \(\text{endpos}(t1)\cap\text{endpos}(t2)=\varnothing\)，要么 \(\text{endpos}(t1)\subseteq \text{endpos}(t2)\)。且 \(t2\in S(t1)\) 是第二個式子成立的充要條件。
當 \(t2\not\in S(t1)\) 時，第一個式子顯然成立。
先證充分性，如果 \(t2\in S(t1)\)，則 \(t1\) 每一次出現 \(t2\) 必定會出現，但 \(t2\) 出現時 \(t1\) 不一定出現。再證必要性，當 \(t2\not\in S(t1)\) 時，第二個式子不成立。
定理二：一個等價類中的所有子串長度排序后一定是連續的。
令 \(t\) 為該等價類中長度最長的子串，那么該等價類中的其他子串一定是它從前往后一段連續的后綴。
to 和 fail
to 邊就是狀態 \(u\) 的子串集合末尾增加 \(c\) 之后（必須還是一個子串）到的一個新的狀態 \(v\)。\(v\) 可能還有從其他狀態增加 \(c\) 之后的子串，所以 \(\text{len}(v)\ge \text{len}(u)+1\)，其中 \(\text{len}(u)\) 表示該等價類中最長子串的長度。
建出來的圖顯然是一個 DAG，并且任意一個子串都能被一條唯一路徑表示。
由于 \(\text{endpos}\) 存在包含關系，所以聯系到 fail 上去想。那么狀態 \(u\) 的 fail 就可以定義為，令 \(t\) 為 \(u\) 中最長的子串，\(t'\) 是 \(t\) 最長的一個后綴且滿足 \(\text{endpos}(t)\subsetneqq\text{endpos}(t')\)，則 \(u\) 的 fail 指向 \(t'\) 所在的等價類 \(v\)。
定理三： fail 形成一棵樹。
定理四：令 \(v\) 是 \(u\) 的 fail，則 \(\text{len}(v)+1=\text{minlen}(u)\)。
因為 \(t'\) 是最長的滿足條件的后綴了，所以它就是 \(v\) 中最長的子串。
推論二：從 \(u\) 跳 fail 直到根，若 \(p\) 在該路徑上，則 \([\text{minlen}(p),\text{len}(p)]\) 互不相交且并集為 \([0,\text{len}(u)]\)。
相當于是連續若干段 \(t\) 的后綴。
流程
跟回文樹的構造類似，用增量式構造。令 \(l\) 為 \(i-1\) 的狀態。當前插入字符為 \(s_i\)。
插入 \(c\) 后肯定會新增一個狀態 \(x\)，即 \(\text{endpose}=\{i\}\)，\(\text{len}(x)=\text{len}(l)+1\)，考慮更新 fail 和 to。
令 \(p=l\)，\(p\) 開始跳 fail，直到 \(to_{p,c}\) 存在，因為如果不存在，則應該在 \(x\) 這個等價類中。如果 \(p\) 一直跳到根都不滿足條件，則說明 \(c\) 第一次出現，直接將 \(f_x\) 設成 \(rt\) 即可。
否則，令 \(q=to_{p,c}\)，如果 \(\text{len}(q)=\text{len}(p)+1\)，那很好，\(q\) 這個等價類在加了 \(c\) 之后 \(\text{endpos}\) 只會增加 \(i\)，所以直接 \(f_x=q\) 即可。
否則，說明 \(\text{len}(q)>\text{len}(p)+1\)，但是對于 \(q\) 中 \(\text{len}>\text{len}(p)+1\) 的子串顯然 \(\text{endpos}\) 是不變的，而其他的子串要歸到增加 \(i\) 之后的等價類里。所以這時候只能將 \(q\) 分裂，新增狀態 \(y\)，表示增加 \(i\) 之后的等價類。\(\text{len}(y)=\text{len}(p)+1\)，根據定義顯然有 \(f_y=f_q\)，\(f_x=f_{q}=y\)。對于 to 的變化，由于它們原本是一個等價類，所以 \(to_y\) 要復制 \(to_q\)。在增加 \(c\) 后，再從 \(p\) 跳 fail，對于 \(to_{p,c}=q\) 的需要改成 \(y\)，因為等價類變了。
廣義后綴自動機
https://www.luogu.com.cn/article/pm10t1pc
對于多個串構建 SAM。
常見有三種做法：
- 到一個新串時，把 \(l\) 設成 \(1\)，然后進行插入。
- 把每個串掛到 Trie 上，按照深度 dfs 插入。
- 把每個串掛到 Trie 上，按照深度 bfs 插入。
第一種和第二種都會出現討論中的問題，會產生空節點。
應用
求本質不同的子串個數。
利用 fail 樹的性質，答案為 \(\sum(\text{len}(i)-\text{len}(f_i))\)。
求位置/本質不同第 \(k\) 大子串。
因為找第 \(k\) 大，考慮確定每一位，從小到大枚舉。則需要知道走一條邊有多少種子串。拓撲圖上算一下就行了。
多數后綴問題常常會建反串的 SAM，fail 樹即為后綴樹。如查詢兩個后綴的 lcp 即為后綴樹上兩個節點的 lca 的長度。
浙公網安備 33010602011771號