后綴數組

初學易混：雖然是給后綴排序，但是每一個后綴的字典序是從前往后看的。

\(rk_i\) 表示 \(suf_i\) 在所有后綴中的排名，\(sa_i\) 表示排名為 \(i\) 的后綴的下標，其中 \(rk\) 與 \(sa\) 互為逆映射。但是在 SA 的建立過程中并不滿足這個性質，因為存在并列排名。

在 SA 的建立過程中，\(rk\) 中存在并列排名就算一個人（也就是說如果兩個并列第三之后還存在第四名），在 \(sa\) 中存在并列算多人（也就是說如果有兩個人并列第三就不存在第四名了）。

建立

簡述一下 SA 的實現方法，就是倍增排序。

每次倍增后要合并相鄰兩段。在前面那段肯定是第一關鍵，后面那段是第二關鍵字。我們在上一次排序之后已經完成了對于小段的排序。一直排序，直到所有段可區分。

這是一些定義，\(rk_i\) 表示下標位置 \(i\) 對應當前所在第一關鍵字的映射，也就是第一關鍵字的排名。\(y_i\) 表示第二關鍵字排名為 \(i\) 的東西第一關鍵字的位置。

先對所有字符離散化一下，按照字符的字典序壓縮進 \([1,\lvert \sum\rvert]\)。

我們先要對單字符特殊預處理一下排名，對于 \(rk\) 數組，\(rk_i\gets s_i\)。然后對應種類的桶 \(++\)，最后對于桶前綴和，然后枚舉 \(i\)，用 \(i\) 更新 \(sa(c_{x_i})\)，同時桶 \(--\)，不斷處理。

然后開始倍增，我們要先更新 \(y_i\)，對于 \(y_i \in [n-k+1,n]\)，我們可以發現他們湊不齊第二關鍵字，空串的字典序小，所以先特判分配一下。然后對于 \(sa_i>k\) 的位置作為第二關鍵字，他們才有第一關鍵字，所以我們依次用 \(sa_i-k\) 更新 \(y\)。接著還是還是想上面那樣處理 \(rk\)，然后在第一關鍵字的前提下排序第二關鍵字 for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i]。由于排序單位長度變化，所以第一關鍵字的種類也要變了，所以我們先復制一下剛剛的 \(rk\) 數組記為 \(rk'\)，當枚舉 \(i\)，當 \(sa(rk'_i)\) 與 \(sa(rk'_i+k)\) 都與 \(i-1\) 的對應信息相同時，下一輪這倆的第一關鍵是相同的所以 \(rk(sa_i)=rk_(sa_{i-1})\)，否則新建一類。如果遇到第一關鍵種類恰好為 \(n\) 就代表已經完成排序了可以退出。

height 數組

定義 \(h_i=\operatorname{lcp}(sa_i,sa_{i-1})\)。對 \(rk\) 有如下性質，

若 \(rk_i<rk_j<rk_k\)，則 \(\operatorname{lcp}(i,j),\operatorname{lcp}(i,j) \ge \operatorname{lcp}(i,k)\)。

由此我們可以推出來一個性質 \(h_{rk_i} \ge h_{rk_{i-1}}-1\)。

于是可以線性求解 \(h\) 數組了。

lcp

兩個后綴之間 \(\operatorname{lcp}\) ，注意要對于 \(i=j\) 特判。

對于 \(rk_i<rk_j,\operatorname{lcp}(i,j)=\min\limits_{k=rk_i+1}^{rk_j}h_k\)。

預處理 ST 表，可以 \(O(1)\) 回答。

如果是求后綴兩兩 \(\operatorname{lcp}\) 之和，可以按照排名加入后綴，\(\sum\limits_{i=2}^n\sum\limits_{j=1}^{i-1}\operatorname{lcp}(sa_j,sa_i)\)。

化簡式子，\(\sum\limits_{i=2}^n\sum\limits_{j=1}^{i-1}\min\limits_{k=j+1}^ih_k\),可以看成不斷加入矩形后的矩形面積和，單調棧維護即可。

本質不同子串數計數

我們發現每個后綴的每個前綴構成了串的所有子串，考慮每次添加一個并且刪除以加入后綴中前綴相同者，也就是 \(\max\limits_{j\in S}\{\operatorname{lcp}(i,j)\}\)。于是我們按照 \(rk\) 值依次加入這樣子上述式子就可以變成 \(h_i\)。

所以就是 \(\begin{pmatrix}n\\2\end{pmatrix}-\sum\limits_{i=2}^n h_i\)。

如果要求某個后綴集合的也是好辦的，我們對于這些后綴集合按照排名排序，設集合大小為 \(m\)，然后就是 \(\sum\limits_{i=1}^m n-p_i+1+\sum\limits_{i=2}^m\operatorname{lcp}(p_{i-1},p_{i})\)。用 ST 表預處理后可以 \(O(m)\) 求解。

最長公共子串

對于多個串插入分隔符建立 SA，然后就是雙指針掃排名區間求區間最小 \(h\)。同時這個區間需要滿足包含所有串的至少一個后綴，容易發現區間滿足雙指針性質，直接雙指針 \(+\) 單調隊列維護即可。

與數據結構結合

區間最小值聯想到笛卡爾樹。

可以根據 \(h\) 數組大小在 \(sa_{i-1}\) 與 \(sa_i\) 之間連邊用并查集之類維護。

例題

P3763 [TJOI2017] DNA

將兩個串拼接在一起，建立 SA。枚舉起始位置，利用 \(\operatorname{lcp}\) 快速匹配，往前跳，如果斷點數 \(\le 3\) 就合法。

P2852 [USACO06DEC] Milk Patterns G

從大到小枚舉 \(h_i\)，然后就相當于在 \(sa_i\) 和 \(sa_{i-1}\) 之間連邊，當出現大小為 \(k\) 的聯通塊的時候，此時的 \(h_i\) 就是答案。

P2463 [SDOI2008] Sandy 的卡片

都加上一個數不太好處理，于是考慮差分數組，然后就是上面的模型了。

P1117 [NOI2016] 優秀的拆分

我們發現對于 "AA" 與 BB”，二者是獨立的。所以我們只需要枚舉分界點，算一下它前面的 "AA" 個數以及它后面的 “BB” 個數。乘起來就行了。

可以笛卡爾樹上+二維數點是 \(2\log\) 的。

可以發現如果我們從尾節點統計很難產生類似一段區間都滿足的情況，于是考慮從中間枚舉。我們可以枚舉長度 \(len\)，然后每隔 \(len\) 個點就設置一個哨兵節點。對于一個合法 \(AA\)，可以發現必然覆蓋至少兩個哨兵節點。于是我們對于兩個哨兵位置查詢 lcs 和 lcp，如果 lcp+lcs \(\ge len\)，那么存在。在第二個哨兵節點后一段區間可以整體加一，差分即可。

P7361 「JZOI-1」拜神

高質量的 SA 練習題。比題庫中的大部分 SA 配合數據結構的無聊套路題多了點變化。

題目即求給定多次區間詢問，其中區間內任意兩個子串的 \(\operatorname{lcp}\) 長度的最大值。

考慮二分答案轉化為判定問題，即求是否存在 \(i,j\in[l,r-ans+1]\)，滿足 \(\operatorname{lcp}(i,j)\ge ans\)。

可以使用 SA 配合上 height 數組的從大到小的啟發式合并很好地刻畫上述條件。

如果存在上述 \(i,j\) 即代表他們倆在同一長度 \(\ge L\) 集合內。如果暴力對于集合內點對進行標記統計是 \(O(n^2)\) 的，很劣。

可以發現如果沒有 \(i,j\) 的范圍要求，那么只需要檢查集合內是否有至少兩個元素即可，這是一個很簡單的問題。于是這啟發我們從這個范圍的約束條件下手，雙變量不妨固定其中的一個，假設我們固定了 \(i\)（其中 \(i<j\)），那么只需要尋找一個 \(j\) 落在 \([i,r-ans+1]\) 的范圍內即可，于是我們可以貪心地維護每個位置的最近后繼問題，然后判定最近后繼是否 \(\le r-ans+1\) 即可。

于是我們就大大減小了問題的規模，從原本的標記所有點對到現在只用考慮維護后繼。

在啟發式合并的過程中，我們是把小集合的元素一一加入大集合中，在這個過程中，每次加入一個元素，二分尋找它在新的集合中的后繼并更新是很簡單的。現在問題來了如何更新大集合中的后繼，我們不可能掃描大集合中的每個元素來尋找后繼，這會使得復雜度不對了。其實仔細思考一下會發現，每個新加入的小集合中的元素其實只會對于它在大集合中的前驅產生貢獻，比如我們加入了 \(k\)，滿足 \(i<j<k\)，\(k\) 只會對于 \(j\) 產生貢獻，因為 對于 \(i\) 來說 \(j\) 比 \(k\) 更優。于是我們在加入小集合元素時查找前驅后驅并相應更新即可。

如果詢問給定了需要判定的長度，那么我們直接離線按照長度從大到小一遍啟發式合并集合一邊回答對應長度的詢問即可。但是因為我們是在二分答案，所以需要在線算法。

可以發現要保留所有長度的信息，這提示了我們要使用可持久化線段樹，每次二分之后在對應長度代表的線段樹上區間查詢所有點的后繼中最小的那個進行判定即可。

時間復雜度 \(O(n\log^2n)\)。

后綴自動機

目的：為了在一個 DAG 上表示一個字符串的所有子串。

為了表示所有子串，我們可以對于所有前綴把它的所有后綴都拉出。采用增量法加入字符，然后加入以這個字符結尾的所有后綴即可。

endpos 集合的構建

最暴力的做法是把 \(S\) 的所有子串抽出來建立一個 AC 自動機。但是這個復雜度顯然不對。我們需要合并相同狀態，最小化 DFA。如果兩個狀態在接受一個相同字符的時候都會轉移到相同狀態或者失配，那么兩個狀態不可區分，可以合并。

對于字符串 \(S\) 的某個子串，其 endpos 集合為它在 \(S\) 中所有出現位置的右端點組成的集合。每次加入 \(O(n)\) 個后綴顯然是無法接受的，有了 endpos 集合，我們就可以合并一些重復的了。

考慮動態構建 endpos 集合，由于我們保存的是右端點所以考慮從 \(r\) 開始往前擴展。我們從可以從 endpos 集合的所有位置出發，設下一個待擴展字符為目標字符，如果所有位置的下一個目標字符都相同那么所有位置都可以向前擴展一位，endpos 集合保持不變，必然存在向后擴展長度在 \([L,R]\) 之內的字符串使得它們的 endpos 集合相同，如果超過了 \(R\) 那么會出現目標字符不同。這樣根據目標字符的種類，大的 endpos 集合會分裂為小集合。

endpos 性質：

1. endpos集相同的子串呈后綴關系。

2. 兩個 endpos 集要么包含要么交集為空，因此根據這個性質任意一個 SAM 的 endpos 集都可以構成樹。

3. endpos 等價類中的串長度連續。

4. endpos 等價類的個數為 \(O(n)\) 級別的。

5. \(\rm {len}(fa_u)+1=\rm {minlen}(u)\)，得到這個結論之后我們就可以只記錄當前等價類的最長長度即可，因為最短長度可以由父節點推出來，而一個等價類中長度又是連續的，故所有信息都知道了。

后綴鏈接樹

現在我們開始建立 parent tree，若 \(v_j\) 由 \(v_i\) 通過上述說法分裂而來的話，那么 \(link(v_j)=v_i\)，\(v_i \to v_j\) 就是樹上的一條邊。每一個點 \(u\) 的不同兒子是從 \(R-len_u\) 位置選擇不同目標字符得到的。這樣子后綴樹就建好了。

于是我們在這棵樹的基礎上建立后綴自動機，自動機涉及子串之間狀態的轉移，類比 ACAM，我們需要求出 \(ch_{u,c}\) 數組，表示在 \(u\) 的狀態上向后添加一個字符 \(c\) 可以轉移到后綴樹上的什么狀態上面。后綴自動機的起始節點是根節點（空），終止節點是 \(S_{[1,n]}\) 在樹上所在節點及其祖先節點。于是我們可以發現延后綴樹上的 \(ch\) 邊走相當于在末尾添加字符，而延樹上邊走相當于在前面添加字符。

SAM 的建立

采用增量法，假設已經構造完了 \(S[1::i]\)，我們現在加入 \(S_{i+1}\)。

我們在末尾添加了一個目標字符 \(c\)，并新開一個節點 \(np\)。我們直接從 \(S[1::i]\) 對應節點開始在樹上跳 link，這相當于由長到短壓縮地遍歷原串的所有后綴 \(S[l,i]\)，\(l\) 遞增。至于為什么是壓縮遍歷，因為我們把很多狀態相同的 \(l\) 合并在了同一個節點。

我們希望加入所有狀態 \(S[l::i+1]\)。同樣的，我們希望把所有狀態相同的 \(l\) 合并在同一個節點。針對 \(S[1::l+1]\) 我們新建一個節點，其 endpos 集合為 \(\{i+1\}\)，不斷跳 \(l\)，如果其沒有連出 \(c\) 邊的情況，說明之前沒有出現過子串 \(S[l::i]+c\)，那么全部都和 \(S[1::i+1]\) 在同一個 endpos 集合 \(\{i+1\}\) 內，這個時候就不需要新建 endpos 節點集合。但是需要連 \(ch_{u,c}\) 邊，全部指向新建的節點就行了。

直到出現一個有 \(c\) 邊的。有一個 corner case 先判掉：如果此時到了根節點就直接將 \(np\) 的父親設置為根。

對于其他情況，說明之前出現過子串 \(S[l::i]+c\)，而且現在其多了一個新 end 節點就是 \(i+1\)，必定會產生新節點，而且注意對于 \(\forall l'\in [l,i]\)，其對應的 \(S[l::i]+c\) 這個子串都會產生新的 endpos 集合。

我們沿著 \(c\) 邊走到一個節點 \(q\)，如果 \(len(q)=len(p)+1\)，說明 \(q\) 恰好只增加了一個 \(c\)，于是 \(q\) 是 \(np\) 的后綴，直接連 link 即可。

否則新建一個等價類，代表在這個位置進行分裂 endpos 集合，分裂出 \(q\) 和 \(np\)，直接把 \(q\) 與 \(np\) 連上去就行了。然后向上跳 link，如果 \(ch_{u,c}\) 指向的是 \(q\)，我們就更新 \(ch_{u,c}\) 連向我們新建立的等價類，否則不更新。

注意連邊的時候 \(fa\) 和 \(ch\) 不是逆數組關系，我們新建的節點 \(nq\) 其父親應該是 \(fa_q\)，而不是 \(ch_{p,c}=q\) 的 \(p\)。

在 link 樹上行走的時候，一個節點會代表多個串（endpos 集合內的串），在 \(ch_{u,c}\) 上面行走的時候當前節點只代表一個串：DAG 前驅上的路徑構成的字符串。

復雜度證明：

后綴鏈接樹的狀態數不超過 \(2n-1\)。后綴樹的 \(n+1\) 的葉子節點代表了從各個位置延伸至開頭的狀態。同時每個非葉子節點至少兩個子節點（這點很重要，如果只有一個子節點那么可以合并），于是整顆樹有不超過 \(2n+1\) 個節點。注意到 \(0\) 可以直接去掉，\(1\) 也就一個點就是葉子節點，于是某個點存在至少三個子節點，所以總節點數不超過 \(2n-1\)。這是后綴鏈接樹的復雜度，SAM 的復雜度我目前不會證。

與 AC 自動機的比較

首先 AC 自動機是多串的，SAM 為單串，但是也可以通過廣義 SAM 變成多串的。

最重要的一點是 AC 自動機一般是整個串產生貢獻，而 SAM 一般為子串產生貢獻。

我們一般有這種題：\(A\) 串在另一個串 \(B\) 中的子串出現。如果從 \(A\) 的角度考慮就建立 ACAM，如果從 \(B\) 的角度考慮就建立 SAM。具體問題具體分析。

廣義后綴自動機

先插入到 Trie 樹上，然后在 Trie 樹上 dfs 的同時建立 GSAM 即可。

在 SAM 中我們有 \(last\)，代表上一個狀態的節點，也就是 \(S[1::i]\) 代表的狀態。這里的 \(last\gets fa_u\)，fa 為 Trie 樹上的父親。

基礎應用

以下基本都是模板題的一些考法，在比賽/正規考試基本不會出現。

一個串在其 link 樹上的所有兒子中都出現過，以下的出現次數類問題都用這個思路來求解。

• 檢查字符串是否作為子串在某個模板串中出現出現。直接在 SAM 上行走即可。

• 不同子串的個數。最直觀的是 \(\sum\limits_u len(u)-len(fa(u))\)。也可以通過遞推解決，\(d_u=1+\sum d_v\)，最后答案是 \(d_{root}-1\)，因為要減去空串。

• 不同子串總長度。可以直接在每個節點處算等差數列，也可以 \(f_u=\sum f_v+d_v\)

注意：以上兩個遞推式中的邊都是 ch 數組里面的。

• 字典序第 \(k\) 大子串，通過 \(d\) 數組來尋找即可。P3975 [TJOI2015] 弦論
  這題的第 \(k\) 大串分相同子串是算一個還是多個。算一個的話很容易，拿 \(d\) 數組解決。如果是算多個的話就需要統計出 endops 集合大小即可，也就是順著 link 樹求和即可。

• 最小表示。建立 \(S+S\) 的 SAM 然后走字典序最短的長度為 \(\lvert S \rvert\) 的路徑即可。

• 子串出現次數，對于每個非復制節點，設 \(sum_p=1\)，然后對于 link 樹跑一遍從底向上求和就行了。

• 第一次出現位置：預處理 \(\rm firstpos\) 對于新建節點就是 \(len\)，對于復制節點就是被復制節點的 \(\rm firstpos\)，答案就是 \(\rm {firstpos}-\lvert p\rvert+1\)。

• 所有出現位置：對著后綴鏈接遍歷即可，如果不是復制節點就輸出。

• 最短未出現字符串：如果不存在一種字符使得 \(u\) 的邊沒有，那么 \(d_u=1\)，否則 \(d_u=\min_{(u,v)\in sam} d_v\)

• 最長公共子串：有邊就走，否則延著后綴鏈接跳，同時縮短長度。如果是多個串就建立廣義 SAM 然后選擇 \(size=n\) 的節點。

• 最長不可重疊重復子串 if(sz[u]>=2) ans=max(ans,min(len[u],r[u]-l[u]));

進階應用

以下是需要重點掌握的在非模板題中的必備技巧。

• 查找子串 \([l,r]\) 位于的節點，記錄所有 \(s[1,r]\) 的節點，然后往上倍增，跳到 \(len\) 合適的地方。

• \(s[l,r]\) 在 \(x\) 之后第一次出現的位置。線段樹合并求出 endpos 集合，然后線段樹二分。

例題

CF1780G Delicious Dessert

在 link 樹上 DP 求出每個子串的出現次數。

使用調和級數標記倍數，處理出 \([1,n]\) 每個數的因數集合，然后直接在因數集合內二分就行了。

CF666E Forensic Examination

對于 \(T\) 建立廣義后綴自動機之后，在 link 樹上使用線段樹合并得到每種串的在各個 \(T\) 的出現次數。

然后對于 \(S\) 在 GSAM 上行走一遍，得到 \(S\) 的每個前綴在后綴自動機上匹配的位置 \(to_x\)。然后對于 \(S\) 的區間 \([l,r]\) 從 \(to_r\) 開始利用字符串長度的比價來樹上倍增得到這個串所屬的節點，在對應節點進行線段樹查詢即可。

注意特判 \(S\) 前綴 \(r\) 的匹配長度小于 \(r-l+1\) 的情況。線段樹合并的時候不能銷毀/改變之前的信息，要新建節點保留之前信息，因為我們是對于所有節點都會進行查詢。

P3346 [ZJOI2015] 諸神眷顧的幻想鄉

其實需要發現本質就是求不同字串的個數?？梢杂脧V義 SAM 求解。

但是我們太不方便跨過 LCA 繞一圈求串。這里有一個結論就是從所有葉子節點出發，可以遍歷到樹上的所有路徑。

而本題中葉子節點數目很少，于是可以直接暴力，題目相當于給定了若干顆 Trie，dfs 的時候合并就行了。

P8947 Angels & Demons

由于 \(T\) 是動態加入的且要求在線，所以不能離線從 \(T\) 角度考慮對于 \(S\) 的貢獻，也就無法使用 AC 自動機了。對于考慮直接從 \(S\) 的子串角度計算答案，因為需要建立廣義 SAM。

本題需要知道的就是一個串在其 link 樹上的子樹內的所有 endpos 集合內出現。

對于 \(S\) 串建立廣義 SAM 之后，動態加入 \(T\) 的時候，就讓 \(T\) 在 GSAM 上順著轉移邊行走，如果失配就跳 fail，并且維護匹配長度。

一個 \(S\) 中的串在當前這個 \(T\) 中出現，需要滿足 \(T\) 的某個狀態存在于 \(S\) 的子樹內（不包含本身節點），或者經過了本身節點且匹配長度大于當前串長。

第一個貢獻形式是子樹數點，第二種貢獻形式就是對于每個點開一個動態開點線段樹維護其每種長度被貢獻次數。但是注意一個 \(T\) 只能貢獻一次，所以需要去重?？紤]提取出 \(T\) 在 GSAM 上行走經過點構成的虛樹，只保留虛樹的葉子節點（否則子孫關系會重復貢獻），對于葉子節點可能被 \(T\) 多次經過，保留最長的匹配長度在線段樹上進行貢獻。注意到兩個葉子會產生重復貢獻，也就是他們 \(\rm LCA\) 以及 \(\rm LCA\) 祖先這一段。于是我們按照 \(\rm DFS\) 序排序之后對于相鄰點在其 \(\rm LCA\) 處差分一下就行了。

時間復雜度單 \(\log\)。

回文自動機

其實可以類比 SAM，二者都是維護子串信息。

在 SAM 中我們維護的 link 表示最長后綴，在 PAM 中我們維護 link 表示最長回文后綴。

注意要建立兩個根節點，分別代表偶串和奇串。

每次往上跳就是看對稱之外的兩個字符是否相同。

P5555 秩序魔咒

兩顆 PAM 上同時 dfs 即可。注意需要對于奇，偶兩個根都跑一遍。