所謂后綴自動(dòng)機(jī)，就是通過后綴建立的自動(dòng)機(jī)

（逃）
請(qǐng)?jiān)试S我先介紹一下后綴家族：

（又逃）

前言

OI生涯目前為止學(xué)習(xí)的最為難以理解的算法，沒有之一。
到現(xiàn)在也沒有完全的理解。
qwq

概念

定義：

后綴 $i$ ：字符串 $s$ 以 $i$ 結(jié)尾的后綴（前綴同理）
$endpos(x)$ 字符串 $x$ 在 $s$ 中出現(xiàn)的結(jié)尾位置的集合
等價(jià)類：若 $endpos(u)=endpos(v)$，我們就稱 $u$ 和 $v$ 屬于同一個(gè)等價(jià)類

不難發(fā)現(xiàn)，對(duì)于 $s$ 的一個(gè)子串 $x=s_{l...r}$，都存在一個(gè)位置 $p\in (l,r]$，滿足對(duì)于 $l\le i\le p$，$x$ 的后綴 $i$ 都與 $x$ 屬于同一個(gè)等價(jià)類，而對(duì)于 $p<i\le r$，后綴 $i$ 與 $x$ 都不屬于一個(gè)等價(jià)類。
我們稱滿足這個(gè)性質(zhì)的 $p$ 為 $link(x)$。

SAM是一個(gè)字符轉(zhuǎn)移邊組成的DAG，每條從根結(jié)點(diǎn)出發(fā)的路徑都唯一對(duì)應(yīng) $s$ 的一個(gè)子串，在SAM中，每個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)等價(jià)類的集合（也就是從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑所代表的字符串的集合，這些字符串必然由一個(gè)最長的字符串和它的一些連續(xù)的后綴組成），一個(gè)結(jié)點(diǎn)的 $link$ 定義為該結(jié)點(diǎn)對(duì)應(yīng)的最長字符串的 $link$。

請(qǐng)務(wù)必確保你理解了上面這段話

構(gòu)建

現(xiàn)在考慮如何構(gòu)建出SAM
使用增量法，當(dāng)前加入一個(gè)新的字符串 $c$
設(shè)上一個(gè)加入的結(jié)點(diǎn)為 $lst$，當(dāng)前加入結(jié)點(diǎn)為 $cur$
設(shè)一個(gè)結(jié)點(diǎn)代表的最長字符串的長度為 $len$

首先，令 $len(cur)\leftarrow len(lst)+1$
然后從 $lst$ 沿著 $link$ 不斷往上跳，直到跳到某個(gè)有 $c$ 的轉(zhuǎn)移邊或者跳到根為止，沿途把 $c$ 的轉(zhuǎn)移邊全部賦值成 $cur$

situation 1

若到根了還沒有 $c$ 的轉(zhuǎn)移邊：說明整個(gè)字符串還沒有出現(xiàn)過 $c$，直接把 $link(cur)$ 賦值成根即可

否則，設(shè)跳到了結(jié)點(diǎn) $p$，$p$ 的 $c$ 轉(zhuǎn)移邊為 $q$
由于一直跳的是

situation 2

若 $len(q)=len(p)+1$：這兩個(gè)結(jié)點(diǎn)在原串上就是相鄰的，直接令 $link(cur)=link(q)$ 即可

situation 3

若 $len(q)=len(p)+1$：這兩個(gè)結(jié)點(diǎn)在原串上不是相鄰的，此時(shí)若按照情況2的處理方法，會(huì)使SAM上出現(xiàn)不應(yīng)該出現(xiàn)的前綴，所以我們應(yīng)該分裂出一個(gè)結(jié)點(diǎn) $pp$，繼承所有 $q$ 的信息，$len(pp)\leftarrow len(p)+1$，并把 $q$ 和 $cur$ 的 $link$ 全指向 $pp$，再一路往上把本來連向 $q$ 的轉(zhuǎn)移連向 $pp$

代碼

void ins(int c){c-='a';int cur=++tot,p=lst;lst=tot;st[cur].len=st[p].len+1;siz[cur]=1;for(;p&&!st[p].tr[c];p=st[p].fa) st[p].tr[c]=cur;if(!st[p].tr[c]) st[cur].fa=1;else{int q=st[p].tr[c];if(st[q].len==st[p].len+1) st[cur].fa=q;else{int pp=++tot;st[pp]=st[q];st[pp].len=st[p].len+1;st[q].fa=st[cur].fa=pp;for(;p&&st[p].tr[c]==q;p=st[p].fa) st[p].tr[c]=pp;return;}} }

應(yīng)用

求 endpos 集合大小

定義 $si{z}_x$ 為結(jié)點(diǎn) $x$ 的等價(jià)類集合中 $endpos$ 的數(shù)目。（也就是出現(xiàn)次數(shù)）
那么根據(jù)定義，有：
$$si{z}_x=\sum _{s\in so{n}_x}si{z}_s+[x\in S]$$
其中 $S$ 是每次插入的終點(diǎn)集合
dfs或者拓?fù)鋵?shí)現(xiàn)均可

int cnt[N],id[N]; void calc(){for(int i=1;i<=tot;i++) ++cnt[st[i].len];for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];for(int i=tot;i>=1;i--) id[cnt[st[i].len]--]=i;for(int i=tot;i>=1;i--) siz[st[id[i]].fa]+=siz[id[i]];return; }

求本質(zhì)不同子串?dāng)?shù)

就是在自動(dòng)機(jī)上的走法種類唄。
那么就有：
$$su{m}_x=\sum _{s=t{r}_{x,c}}su{m}_s+1$$

Thanks for reading!

后綴樹

本身也是一個(gè)大算法，但是可以通過反串建SAM偷懶。
復(fù)雜度為 $O(nC)$。

解析

對(duì)反串建出后綴自動(dòng)機(jī)，其 $fail$ 樹即為所求的后綴樹。
設(shè) $p{l}_x$，為 $x$ 節(jié)點(diǎn)對(duì)應(yīng)的任意一個(gè)出現(xiàn)位置，那么 $fai{l}_x\to x$ 這條邊上對(duì)應(yīng)的字符串就是 $s(p{l}_x+le{n}_{fai{l}_x},p{l}_x+le{n}_x?1)$。
結(jié)合 $fail$ 的定義應(yīng)該不難得到。

后綴樹的性質(zhì)：

根到葉子的路徑和所有后綴一一對(duì)應(yīng)。

所有非根節(jié)點(diǎn)都至少有兩個(gè)子節(jié)點(diǎn)。

$LCP(i,j)$ 就是兩個(gè)位置對(duì)應(yīng)節(jié)點(diǎn) lca 的最長長度。

在解決字典序相關(guān)問題時(shí)較為常用。

總結(jié)

以上是生活随笔為你收集整理的模板：后缀自动机（SAM）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。