寫在前面

后綴自動機，簡稱$SAM$,是一種十分優(yōu)秀的字符串匹(shu)配(ju)算(jie)法(gou)

字符串界的$boss$，幾乎可以解決全部正常的字符串題目

至少我前前后后學(xué)了一年，聽過$4$次課，幾度懷疑自己不適合$oi$

請做好心理準(zhǔn)備

定義

有限狀態(tài)自動機

不管，可以理解為有向圖。

唯一的區(qū)別是信息儲存在邊上，每個點有字符集個數(shù)的轉(zhuǎn)移到若干其他點，類比字典樹。

如果對于一個字符串，沿著每個點的轉(zhuǎn)移走，如果不出界，稱該自動機可以表示這個字符串。

以下將“點”稱為狀態(tài)

能干啥

后綴自動機能表示母串的所有子串。

算法流程

首先明確一點：子串規(guī)模是$O(N^2)$的

所以一個狀態(tài)必須表示多個子串

也就是說，我們要定義出等價的子串

對于一個子串$S$，定義$endpos(S)$為$S$在原串中所有出現(xiàn)的結(jié)束位置的集合

每個狀態(tài)與一個$endpos$集合一一對應(yīng)。即一個狀態(tài)表示一個$endpos$集合。

需要注意的是，$endpos$是完全虛構(gòu)的，在代碼中不會出現(xiàn)。

然后可以表示所有$endpos$等于它的字符串，稱這些子串為一個$endpos$等價類

轉(zhuǎn)移

此時我們定義轉(zhuǎn)移為這個類所有串加上這個字符后所在的轉(zhuǎn)移。

一個類的同一個轉(zhuǎn)移是相同的，因為向$c$的轉(zhuǎn)移的本質(zhì)是當(dāng)前$endpos$整體后移一位的所有$c$的位置。

感性理解。

兩個性質(zhì)

1.兩個子串$S_1,S_2$滿足$S_1$是$S_2$的后綴，當(dāng)且僅當(dāng)$endpos(S_2)?endpos(S_1)$

$S_2$出現(xiàn)的地方一定有$S_1$出現(xiàn)，但有$S_1$出現(xiàn)的地方不一定有$S_2$

2.一個等價類中的子串均為該類中最長串的后綴且長度連續(xù)

第一個顯然

對于一個串$S$，若有后綴$S_1$長度小于$S$,且$S_1$和$S$是等價類

設(shè)$S_2$為長度在它們之間的后綴

有$endpos(S)?endpos(S_2)?endpos(S_1)$

因為$endpos(S)=endpos(S_1)$

所以$endpos(S)=endpos(S_2)=endpos(S_1)$

說明它們之間的串都是一個等價類

Parent鏈

由于類中的長度只有一段，逼死強迫癥

所以我們定義每個狀態(tài)$S$的$fail$指針

滿足$endpos(S)\in endpos(fail(S))$

且$fail(S)$要盡量靠后

可以理解為：從一個狀態(tài)沿$fail$往上跳，取出該類中的所有串，你將會見證這個串不斷失去第一個字符，不斷變?yōu)楹缶Y，最后變成空串。我們稱這條鏈為$parent$鏈。

先放個圖，以$AAB$為栗子

可能看不出啥，但有個大概印象吧

構(gòu)造算法

SAM 采用增量算法，即一個一個字符插入

這使得 SAM 擅長處理動態(tài)問題

現(xiàn)在假設(shè)插入第$i$個字符，前$i?1$個的 SAM 已經(jīng)建立好

首先，上一個插入的點是整個串所在的狀態(tài)，記為$p$

新建一個節(jié)點，記為$cur$。顯然$cur$最長的長度為當(dāng)前串的長度。

由于其他子串已經(jīng)處理了，我們要做的，就是搞出當(dāng)前串的后綴

此處分$3$種情況

①最簡單的情況

栗子：$\text{AA}$插入$\text{B}$

此時$cur$是$\{3\}$

由于每個類里的字符串是等價的（感性理解）

我們可以找到舊的串的所有后綴，給它加上新的字符

也就是讓$p$沿著$fail$不斷跳，令$ch[p][S[i]]=cur$

即：原來的所有后綴加上新來的字符就成了新的后綴

最后$fail(cur)=1$，完結(jié)撒花

②然而這只是最簡單的情況

栗子：$\text{AA}$插入$\text{A}$

沒區(qū)別

咦？已經(jīng)有轉(zhuǎn)移了呀

說明什么？

說明現(xiàn)在新串的這個后綴已經(jīng)在之前的串中出現(xiàn)了

那這個后綴的后綴也一定出現(xiàn)了

（請擺脫這個栗子）

記$q=ch[p][S[i]]$

上面的話翻譯一下，$p$表示的串$+S[i]$已經(jīng)出現(xiàn)了

而這個玩意就是$q$

……嗎？

$p$的最長串$+S[i]$一定在$q$上(定義)，但不一定是$q$最長的

先討論是最長的的情況

$yy$一下，我們要找的后綴不就是$q$的最長串嗎？

而這個后綴的后綴，也就是我們后面要找的，就在$q$的$parent$鏈上

這么說來，我們令$fail[cur]=q$就好了

over

③然而還有個最復(fù)雜的情況

也就是上面的不是$q$最長的

栗子：$\text{AAB}$加$\text{B}$

走程序

停

此時的$q$有$\text{B,AB,AAB}$

而我們的$cur$只想要$\text{B}$和鏈上的東西

怎么辦？

拆了唄

記新建的點為$q^{\prime }$

維護信息

首先$cur$要的是$q^{\prime }$和$q$祖先上的

然后我們發(fā)現(xiàn)$q$和$q^{\prime }$有后綴關(guān)系

接下來維護轉(zhuǎn)移

$q和q^{\prime }$是同一個分出來的，而它們原來的轉(zhuǎn)移共同構(gòu)成了后面的狀態(tài)

現(xiàn)在它們拆開了，理應(yīng)維護好后面

即：將$q$的轉(zhuǎn)移拷貝給$q^{\prime }$

考慮這樣的事實：在前面某個位置，原來轉(zhuǎn)移到了這個狀態(tài)。現(xiàn)在這個狀態(tài)分了，需要考慮具體轉(zhuǎn)移到哪一邊。

注意到轉(zhuǎn)移到$q^{\prime }$而不轉(zhuǎn)移到$q$，當(dāng)且僅當(dāng)這個狀態(tài)最長串長小于$q^{\prime }$最長串長。

并且都是$q$去掉末尾的一個字符后的后綴

根據(jù)意識流這樣的狀態(tài)最后面的滿足的剛好是$p$

而剩下的都在$p$的$parent$鏈上

即：跳$p$的$parent$鏈，如果有到$q$的轉(zhuǎn)移，將它改到$q^{\prime }$

因為是后綴，所以一定是$S[i]$的轉(zhuǎn)移（因為$ch[p][S[i]]=q$）

至此，SAM 就構(gòu)造完畢了

復(fù)雜度是$O(N)$的，顯然我不會證

代碼

具體實現(xiàn)的時候，每個節(jié)點只記錄最長串的長度$le{n}_i$

int fa[MAXN],ch[MAXN][26]; int len[MAXN],last=1,tot=1; int siz[MAXN],a[MAXN],c[MAXN]; void insert(int c) {int p=last,cur=++tot;len[cur]=len[last]+1;last=cur;for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;//跳failif (!p) fa[cur]=1;//情況1else{int q=ch[p][c];if (len[p]+1==len[q]) fa[cur]=q;//情況2else//情況3{int clone=++tot;len[clone]=len[p]+1;for (int i=0;i<26;i++) ch[clone][i]=ch[q][i];fa[clone]=fa[q];fa[q]=fa[cur]=clone;for (;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;} } }

運用

劈配子串

按照定義，沿著轉(zhuǎn)移走

最長公共子串

建出$S$的后綴自動機，拿$T$去跑

不斷用$le{n}_i$更新答案

如果走不動了就跳$fail$

處理出現(xiàn)次數(shù)

對于每一次插入，一個類出現(xiàn)次數(shù)增加，當(dāng)且僅當(dāng)這是當(dāng)前的后綴

也就是把這個點的$parent$鏈都$+1$

顯然會$T$。于是先建完，按長度瞎排個序，倒著往上推。

這樣$si{z}_i$表示狀態(tài)$i$中的一個串的出現(xiàn)次數(shù)。顯然它們是一樣的。

應(yīng)該是用的最多的。

void query() {for (int i=1;i<=tot;i++) c[len[i]]++;for (int i=1;i<=n;i++) c[i]+=c[i-1];for (int i=1;i<=tot;i++) a[c[len[i]]--]=i;for (int i=tot;i>=1;i--) siz[fa[p]]+=siz[p]; }

然后你就可以處理各種沙雕的字符串題

本質(zhì)不同的串的個數(shù)

由于一個串只會被表示一遍

我們相當(dāng)于求所有狀態(tài)表示的串的個數(shù)之和。

即$\sum (len[p]?len[fa[p]])$

Link Cut Tree維護parent鏈

先寫到這里吧，想到再補。

總結(jié)

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

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