?

后綴自動機詳解

標簽：?后綴自動機 2017-03-26 11:34?2341人閱讀?評論(3)?收藏?舉報 ?分類： 后綴自動機（11）?

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

后綴自動機

后綴自動機（單詞的有向無環圖）——是一種強有力的數據結構，讓你能夠解決許多字符串問題。

例如，使用后綴自動機可以在某一字符串中搜索另一字符串的所有出現位置，或者計算不同子串的個數——這都能在線性

時間內解決。

? ?直覺上，后綴自動機可以被理解為所有子串的簡明信息。一個重要的事實是，后綴自動機以壓縮后的形式包含了一個長度

為n的字符串的所有信息，僅需要O(n)的空間。并且，它能在O(n)時間內被構造（如果我們將字母表的大小k視作常數，否則就

是O(n*logk)）。

? ?歷史上，Blumer等人于1983年首次提出了后綴自動機的線性規模，然后在1985-1986年，人們提出了首個線性時間內構建

后綴自動機的算法（Crochemore，Blumer等）。在文末鏈接處查看更多細節。

? ?后綴自動機在英文中被稱作“suffix automaton”（復數形式：suffix automata），單詞的有向無環圖——"direcged acyclic

word graph"（簡寫為“DAWG”）。

后綴自動機的定義

定義.對給定字符串s的后綴自動機是一個最小化確定有限狀態自動機，它能夠接收字符串s的所有后綴。

下面解釋這一定義：

·????????后綴自動機是一張有向無環圖，其中頂點是狀態，而邊代表了狀態之間的轉移。

·????????某一狀態t_0被稱作初始狀態，由它能夠到達其余所有狀態。

·????????自動機中的所有轉移——即有向邊——都被某種符號標記。從某一狀態出發的諸轉移必須擁有不同的標記。（另一方面，

狀態轉移不能在任何字符上）。

·????????一個或多個狀態被標記為終止狀態。如果我們從初始狀態t_0經由任意路徑走到某一終止狀態，并順序寫出所有經過邊的

標記，你得到的字符串必然是s的某一后綴。

·????????在符合上述諸條件的所有自動機中，后綴自動機有這最少的頂點數。（后綴自動機并不被要求擁有最少的邊數）

后綴自動機的最簡性質

最簡性——后綴自動機的最重要性質是：它包含了所有s的子串的信息。換言之，對于任意從初始狀態t_0出發的路徑，如果我們

寫出所經過邊上的標記，形成的子串必須是s的子串。相應地，s的任意子串都對應一條從初始狀態t_0出發的路徑。

為了簡化說明，我們稱子串“匹配”了從初始狀態出發的路徑，如果該路徑上的邊標記組成了這一子串。相應地，我們稱任意路徑

“匹配”某一子串，該子串由路徑中邊的標記組成。

?后綴自動機的每個狀態都引領一條或多條從初始狀態出發的路徑。我們稱這個狀態有若干匹配這些路徑的方法。

?

構建后綴自動機的實例

下面給出一些對簡單的字符串構建后綴自動機的例子。

?初始狀態被記作t0，終止狀態用星號(*)標記。

s=""

s="a"

s="aa"

s="ab"

s="aba"

s="abb"

s="abbb"

一個線性時間構建后綴自動機的算法

在我們描述構建算法之前，有必要介紹一些新的概念和簡要的證明，它們對理解后綴自動機的概念十分重要。

?

結束位置endpos，它們的性質及與后綴自動機的聯系：

考慮字符串s的任意非空子串t。我們稱終點集合endpos(t)為：s中所有是t出現位置終點的集合。

我們稱兩個子串t_1和t_2“終點等價”，如果它們的終點集合一致：endpos(t_1)=endpos(t_2)。因此，所有s的非空子串可

以根據終點等價性分成若干類。

?事實上對后綴自動機，終點等價字符串仍然保持相同性質。換句話說，后綴自動機中狀態數等價于所有子串的終點等價類

個數，加上初始狀態。每個狀態對應一個或多個擁有相同終點集合的子串。

? 我們將這一陳述作為假定，然后描述一個基于此假設的，線性時間構建后綴自動機的算法——正如我們不久后將會看到的，

所有后綴自動機的必須性質，除最小性（即最少頂點數），都將被滿足（最小性由Nerode產生，見參考文獻）。

?關于終點集合，我們給出一些簡單但重要的事實。

引理1.兩個非空子串u和v（length(u)<=length(v)）是終點等價的，當且僅當u在字符串s中僅作為w的后綴出現。

?

證明是顯然的。

?

引理2.考慮兩個非空子集u,w（length(u)<=length(w)）。它們的終點集合不相交，或者endpos(w)是endpos(u)的子集。進一

步地，這取決于u是否是w的后綴：

證明.假設兩個集合endpos(u)和endpos(w)有至少一個公共元素，這就意味著字符串w和u在同一位置結束，即u是w的后綴。

因此，在字符串w的每次出現的終點u都會出現，這就意味著endpos(w)包含于endpos(u)。

?

引理3.考慮一個終點等價類。將該等價類中的子串按長度遞減排序。排序后的序列中，每個子串將比上一個子串短，從而是

上一個字串的后綴。換句話說，某一終點等價類中的字符串互為后綴，它們的長度依次取區間[x,y]內的所有數。

?

證明.考慮這個終點等價類。如果它只包含一個子串，那么引理3的正確性顯然。假設現在子串的個數多于一個。

?

根據引理1，兩個不同的終點等價子串總滿足一個是另一個的嚴格后綴。因此，在同一終點等價類中的子串不可能有相同的長

度。

?令w較長，u是等價類中的最短子串。根據引理1，u是w的嚴格后綴。考慮w任意一個長度為[length(u),length(w)]之間的后綴，

由引理1，顯然它在終點等價類中。

?

后綴鏈接

考慮一個狀態v≠t_0.就我們目前所知，有一個確定的子串集合，其中元素和v有著相同的終點集合。并且，如果我們記w是其

中的最長者，其余子串均是w的后綴。我們還知道w的前幾個后綴（按照長度降序）在同一個終點等價類中，其余后綴（至少包括

空后綴）在別的終點等價類中。令t是第一個這樣的后綴——對它我們建立后綴鏈接。

? 換言之，v的后綴鏈接link(v)指向在不同等價類中的w的最長后綴。

?在此我們假設初始狀態t_0在一個單獨的終點等價類中（僅包含空字符串），并且endpos(t_0)={-1,...,length(s)-1}。

?

引理4.后綴鏈接組成了一棵以t_0為根的樹。

?

證明.考慮任意狀態v≠t_0.后綴鏈接link(v)指向的狀態所對應的字符串長度嚴格小于它本身（根據后綴鏈接的定義和引理3）。

因此，沿著后綴鏈接移動，我們將早晚到達t_0，它對應一個空串。

?

引理5.如果我們將所有合法的終點集合建成一棵樹（使得孩子是父母的子集），這棵樹將和后綴鏈接構成的樹相同。

?

證明.終點集合能構成一棵樹這一事實由引理2得出（兩個終點集合要么不相交，要么一個包含另一個）。

?

我們現在考慮任意狀態v≠t_0，及其后綴鏈接link(v)。根據后綴鏈接的定義和引理2得出：

endpos(v)?endpos(link(v))

這和上一引理證明了我們的斷言：后綴鏈接樹和終點集合樹相同。

?

這里是一個后綴鏈接的例子，表示字符串"abcbc"：

小結

在學習具體算法之前，總結上面積累的知識，并引入兩個輔助符號。

?

·????????s的所有子串可以按照它們的終點集合被分成等價類。

·????????后綴自動機由一個初始狀態t_0和所有不同的終點等價類所對應的狀態組成。

·????????每個狀態v對應一個或多個字符串，我們記longest(v)是其中最長者，len(v)是其長度。我們記shortest(v)是這些字符串中

的最短者，其長度為minlen(v)。

·????????該狀態對應的所有字符串是longest(v)的不同后綴，并且包括[minlen(v),len(v)]之間的所有長度。

·????????對每個狀態v≠t_0定義的后綴鏈接指向的狀態對應longest(v)的長度為minlen(v)-1的后綴。后綴鏈接形成一棵以t_0為根的

樹，而這棵樹事實上是所有終點集合的樹狀包含關系。minlen(v)和link(v)的關系表示如下：minlen(v)=len(link(v))+1.

·????????如果我們從任意節點v_0開始沿后綴鏈接移動，我們早晚會到達初始狀態t_0.在此情況下，我們得到了一系列不相交的區

間[minlen(v_i),len(v_i)]，其并集是一個連續區間。

?

一個構建后綴自動機的線性時間算法

我們下面描述這個算法。算法是在線的，即，逐個向s中加入字符，并適當地對當前的自動機進行修改。

?為了達到線性空間的目的，我們將只存儲每個狀態的len，link的值，以及轉移列表。我們并不支持標記終止狀態（我們將

展示如果需要，如何在后綴自動機構建完畢后加上這些標記）。

?最初自動機由一個狀態t_0組成，我們稱之為0狀態（其余狀態將被稱作1,2,...）。對此狀態，令len=0，為方便起見，將link

值設為-1（指向一個空狀態）。

?因此，現在的任務就變成了實現向當前字符串末尾添加一個字符c的操作。

下面我們描述這一操作：

·???????1.?令last為對應整個字符串的狀態（最初last=0，在每次字符添加操作后我們都會改變last的值）。

·????????2.建立一個新的狀態cur，令len(cur)=len(last)+1，而link(cur)的值并不確定。

·???????3.?我們最初在last，如果它沒有字符c的轉移，那就添加字符c的轉移，指向cur，然后走向其后綴鏈接，再次檢查——如果沒

有字符c的轉移，就添加上去。如果在某個節點已有字符c的轉移，就停止，并且令p為這個狀態的編號。

·????????4.如果“某節點已有字符c的轉移”這一事件從未發生，而我們來到了空狀態-1（經由t_0的后綴指針前來），我們簡單地令link(cur)=0，

跳出。

·????????5.假設我們停在了某一狀態q，是從某一個狀態p經字符c的轉移而來。現在有兩種情況：len(p)+1=len(q)或不然。

·????????6.如果len(p)+1=len(q)，那么我們簡單地令link(cur)=q，跳出。

·????????7.否則，情況就變得更加復雜。必須新建一個q的“拷貝”狀態：建立一個新的狀態clone，將q的數據拷貝給它（后綴鏈接，以及

轉移），除了len的值：需要令len(clone)=len(p)+1.

·????????8.在拷貝之后，我們將cur的后綴鏈接指向clone，并將q的后綴鏈接重定向到clone。

·????????9.最終，我們需要做的最后一件事情就是——從p開始沿著后綴鏈接走，對每個狀態我們都檢查是否有指向q的，字符c的轉移，

如果有就將其重定向至clone（如果沒有，就終止循環）。

·????????10.在任何情況下，無論在何處終止了這次添加操作，我們最后都將更新last的值，將其賦值為cur。

如果我們還需要知道哪些節點是終止節點而哪些不是，我們可以在構建整個字符串的后綴自動機之后找出所有終止節點。對此我們

考慮對應整個字符串的節點（顯然，就是我們儲存在變量last中的節點），我們沿著它的后綴鏈接走，直到到達初始狀態，并且將

途徑的每個節點標記為終止節點。很好理解，如此我們標記了字符串s所有后綴的對應狀態，也就是我們想要找出的終止狀態。

?

在下一節中我們從細節上考慮算法的每一步，并證明其正確性。

這里我們僅注意一點：每個字符的添加會導致向自動機中添加一個或兩個狀態。因此，狀態數顯然是線性的。?

轉移數量的線性性，以及算法的線性時間復雜度較難理解，它們將在下面被證明，位于算法正確性的證明之后。

算法的正確性證明

·????????我們稱轉移(p,q)是連續的，如果len(p)+1=len(q)。否則，即len(p)+1<len(q)時，我們稱之為不連續轉移。

·????????正如在算法描述中可以看到的那樣，連續轉移和不連續轉移導致了算法流程的不同分支。連續轉移）被如此命名是因為，自第

一次出現后，它們將保持不變。相反，不連續轉移可能會在向字符串中添加新字符的過程中被改變（可能會改變該邊指向的狀態）。

·????????為了避免歧義，我們稱s是我們已經構建了自動機的字符串，它正準備添加當前字符c。

·????????算法開始時我們創建了新狀態cur，它將匹配整個字符串s+c。我們之所以必須新建一個狀態的原因是顯然的——在添加新字

符后，出現了一個新的終點等價類——一類以新字符串s+c的末尾為結尾的子串。

·????????在創建新狀態后，算法從和整個字符串s匹配的狀態開始，沿著后綴鏈接移動，在途中試圖添加指向cur的，字符c的轉移。但

我們只會在不和已存在轉移沖突的情況下添加新的轉移，因此一旦我們遇到了一個字符c的轉移，我們就必須立刻停止。

·????????最簡單的情形——如果我們來到了空狀態-1，向途中所有節點添加了字符c的轉移。這就意味著字符c在字符串s中先前未曾出

現。我們成功地添加了所有的轉移，只需要記下狀態cur的后綴鏈接——它顯然必須等于0，因為這種情況下cur匹配字符串s+c的一

切后綴。

·????????第二種情況——當我們進入一個已存在的轉移(p,q)時。這意味著我們試圖向字符串中添加字符x+c（其中x是字符串s的某一后

綴，長度為len(p)），且該字符串先前已經被加入了自動機（即，字符串x+c已經作為子串包含在字符串s中）。因為我們假設字符

串s的自動機已被正確構建，我們并不應該添加新的轉移。
然而，cur的后綴鏈接指向哪里有一定復雜性。我們需要將后綴鏈接指向一個長度恰好和x+c相等的狀態，即，該狀態的len值必

須等于len(p)+1.但這樣一種情況可能并不存在：在此情況下我們必須添加一個“分割的”狀態。

·????????因此，一種可能的情形是，轉移(p,q)變得連續，即，len(q)=len(p)+1.在這種情況下，事情變得簡單，不必再進行任何分割，

我們只需要將cur的后綴鏈接指向q。

·????????另一種更復雜的情況——當轉移不連續時，即len(q)>len(p)+1.這意味著狀態q不僅僅匹配對我們必須的，長度len(p)+1的子串

w+c，它還匹配一個更長的子串。我們不得不新建一個“分割的”狀態q：將子串分割成兩段，第一段將恰在長度len(p)+1處結束。

如何實現這個“分割”呢？我們“拷貝”一個狀態q，將其復制為clone，但參數len(clone)=len(p)+1.我們將q的所有轉移復制給clone，

因為無論如何我們不想改變經過p的路徑。從clone出發的后綴鏈接總是指向q原先的后綴鏈接，而且q的后綴鏈接將指向clone。

在拷貝之后，我們將cur的后綴鏈接指向clone——我們拷貝它就是為了干這個的。

?最后一步——重定向一些指向q的轉移，將它們改為指向clone。哪些轉移必須被重定向？只需要重定向那些匹配所有w+c的后

綴的。即，我們需要持續沿著后綴鏈接移動，從p開始，只要沒有到達空狀態-1或者沒有到達一個狀態，其c的轉移指向不同于q的

狀態。

?

證明操作個數是線性的

首先，我們曾經說過要保證字母表的大小是常數。否則，那么線性時間就不再成立：從一個頂點出發的轉移被儲存在B-樹中，

它支持按值的快速查找和添加操作。因此，如果我們記字母表的大小是k，算法的漸進復雜度將是O(n*logk)，空間復雜度O(n)。但

是，如果字母表足夠小，就有可能犧牲部分空間，不采用平衡樹，而對每個節點用一個長度為k的數組（支持按值的快速查找）和一

個動態鏈表（支持快速遍歷所有存在的鍵值）儲存轉移。這樣O(n)的算法就能夠運行，但需要消耗O(nk)的空間。

因此，我們假設字母表的大小是常數，即，每個按字符查詢轉移的操作、添加轉移、尋找下一個轉移——所有這些操作我們都

認為是O(1)的。

?如果我們觀察算法的所有部分，會發現其中三處的線性時間復雜度并不顯然：

?

·????????第一處：從last狀態開始，沿著后綴鏈接移動，并且添加字符c的轉移。

·????????第二處：將q復制給新狀態clone時復制轉移。

·????????第三處：將指向q的轉移重定向到clone。

我們使用眾所周知的事實：后綴自動機的大小（狀態和轉移的數目）是線性的。（對狀態個數是線性的證明來自算法本身，對于

轉移個數是線性的證明，我們將在下面給出，在實現算法之后。）。

? 那么顯然第一處和第二處是漸進線性的，因為每次操作都會增加新的狀態和轉移。

? 仍然需要估算第三處總的線性復雜度——在每次添加字符時我們將指向q的轉移重定向至clone。

?我們不妨關注shortest(link(last))。注意到，在沿著后綴鏈接上溯的過程中，當前節點的shortest的長度總是嚴格變小。

?顯然，在向s中添加新字符之前，shortest(link(last))的長度不小于shortest(p)的長度，因為link(last)至多是p。爾后假設我們由q

拷貝得到了節點clone，并試圖從p沿后綴鏈接上溯，將所有通往q的轉移重定向為通往clone。設v是shortest(當前節點)，在clone剛

剛建立完成后，v=short(p)。然后，在每次沿后綴鏈接上溯時，v的值都會變小，而如果當前節點存在經過字符c通往q的轉移，就意

味著q對應的字符串集合中包含v+c，也意味著clone包含的字符串集合中包含v+c。換言之，我們為clone包含的字符串集合找到了一

個更短的元素，即減少了short(clone)的長度。

在“向s中添加新字符”的整個流程結束后，有link(last)=link(cur)=clone。根據上面的討論，新的shortest(link(last))的長度變小（或

保持不變），而且這一長度減小的值和上溯的操作數同階。

?綜上，shortest(link(last))作為s一個后綴的起始位置在整個過程中不斷右移，而且每次沿后綴指針上溯都會導致該位置嚴格右移。

由于在程序結束時這一起始位置不超過n，所以這一過程的時間復雜度是線性的。

?（雖然沒什么用，但同樣的討論可以被用來證明第一處的線性性，以代替對狀態個數線性性的證明。）

?

算法的實現

首先我們描述一個數據結構，它儲存特定的一段信息(len,link,轉移列表)。如有必要，你可以增加表示終止狀態的標簽，以及其他需要

的信息。

我們用STL容器map存儲轉移列表，其空間復雜度為O(n)，而處理整個字符串的時間復雜度為O(n*logk)。

[cpp]?view plaincopy

1. struct?state?{??
2. ????int?len,link;??
3. ????map<char,int>?next;??
4. };??

后綴自動機本身將被儲存在一個state類型的數組中。正如下一節中將證明的那樣，如果程序中所處理字符串的最大可能長度是MAXN，

那么至多會占用2*MAXN-1個狀態。同時，我們儲存變量last——當前匹配整個字符串的狀態。

[cpp]?view plaincopy

1. const?int?MAXLEN?=?100000;??
2. state?st[MAXLEN*2];??
3. int?sz,?last;??

我們給出初始化后綴自動機的函數（新建一個初始狀態）：

[cpp]?view plaincopy

1. void?sa_init()?{??
2. ???sz?=?last?=?0;??
3. ???st[0].len?=?0;??
4. ???st[0].link?=?-1;??
5. ???++sz;??
6. ????/*?
7. ????//?若關于不同的字符串多次建立后綴自動機，就需要執行這些代碼：?
8. ????for?(int?i=0;?i<MAXLEN*2;?++i)?
9. ????????st[i].next.clear();?
10. ????*/??
11. }??

最后，我們給出基礎函數的實現——向當前字符串的尾部添加一個字符，并相應地修改后綴自動機：

[cpp]?view plaincopy

1. void?sa_extend?(char?c)?{??
2. ????int?cur?=?sz++;??
3. ????st[cur].len?=?st[last].len?+?1;??
4. ????int?p;??
5. ????for?(p=last;?p!=-1?&&?!st[p].next.count(c);?p=st[p].link)??
6. ????????st[p].next[c]?=?cur;??
7. ????if?(p?==?-1)??
8. ????????st[cur].link?=?0;??
9. ????else?{??
10. ????????int?q?=?st[p].next[c];??
11. ????????if?(st[p].len?+?1?==?st[q].len)??
12. ????????st[cur].link?=?q;??
13. ????????else?{??
14. ????????int?clone?=?sz++;??
15. ????????????st[clone].len?=?st[p].len?+?1;??
16. ????????????st[clone].next?=?st[q].next;??
17. ????????????st[clone].link?=?st[q].link;??
18. ????????????for?(;?p!=-1?&&?st[p].next[c]==q;?p=st[p].link)??
19. ????????????st[p].next[c]?=?clone;??
20. ????????????st[q].link?=?st[cur].link?=?clone;??
21. ????????}??
22. ????}??
23. ????last?=?cur;??
24. }??

像前面提到的那樣，如果犧牲部分空間（空間復雜度增至O(nk)，其中k是字母表大小），就能夠對任何k實現O(n)構建自動機——但這將

會在每個狀態中建立一個長度為k的數組（用于快速按字符查詢轉移）和一個轉移鏈表（用于快速遍歷或者復制所有轉移）。

后綴自動機的其他性質

狀態的數量

由長度為n的字符串s建立的后綴自動機的狀態個數不超過2n-1（對于n>=3）。

上面描述的算法證明了這一性質（最初自動機包含一個初始節點，第一步和第二步都會添加一個狀態，余下的n-2步每步至多由于需要分割，增加兩個狀態）。

不過，即使不涉及算法，這一性質也容易證明。注意到狀態個數等于不同的終點集合的個數。此外，終點集合按“子女是父節點的不同子集”這一原則構成一棵樹。

考慮這棵樹，將其稍作擴充：若一個內部節點只有一個兒子，那就意味著該兒子的終點集合不包含其父親終點集合中的至少一個值；那么我們就創建一個虛擬節點，

其終點集合為這個值。最終，我們得到了一棵樹，其內部節點度數均>1，而葉子節點個數不超過n。因此，這棵樹的結點個數不超過2n-1.自然，原樹的結點個數也

不超過2n-1.

這樣我們就獨立于算法地證明了這一性質。

有趣的是，這一上限無法被改善，即存在達到這一上限的例子：?

"abbbb..."

從第三次開始，每次添加字符時都會進行分割，因此結點個數將達到2n-1.

轉移的數量

由長度為n的字符串s建立的后綴自動機中，轉移的數量不超過3n-4（對于n>=3）。

?

證明.

?我們計算“連續的”轉移個數。考慮以t_0為初始節點的自動機的最長路徑樹。這棵樹將包含所有連續的轉移，樹的邊數比結點個數小1，這意

味著連續的轉移個數不超過2n-2.

? ?我們再來計算不連續的轉移個數。考慮每個不連續轉移；假設該轉移——轉移(p,q)，標記為c。對自動機運行一個合適的字符串u+c+w，其

中字符串u表示從初始狀態到p經過的最長路徑，w表示從q到任意終止節點經過的最長路徑。一方面，對所有不連續轉移，字符串u+c+w都是不同

的（因為字符串u和w僅包含連續轉移）。另一方面，每個這樣的字符串u+c+w，由于在終止狀態結束，它必然是完整串s的一個后綴。由于s的非

空后綴僅有n個，并且完整串s不能是某個u+c+w（因為完整串s匹配一條包含n個連續轉移的路徑），那么不連續轉移的總共個數不超過n-1.

? ?將這兩個限制加起來，我們就得到了總數限制3n-3.注意到雖然狀態個數限制可以被數據"abbbb..."達到，但這個數據并未達到3n-3的轉移個數

上限。它的轉移個數是3n-4，符合要求。

? ?有趣的是，仍然存在達到轉移個數上限的數據：

"abbb...bbbc"。

與后綴樹的聯系，在后綴自動機上建立后綴樹及反之

? ?我們證明兩個定理，它們能說明后綴樹和后綴自動機之間的相互關系。

首先我們假定輸入字符串的每個后綴都在其后綴樹中對應一個節點（對于任意字符串而言并不一定成立：例如，對于字符串 "aaa..."）。在后綴

樹的典型實現中，我們通過在字符串的末尾加上一個特殊符號（例如"#"或"$"）來保證這一點。

? ?方便起見，我們引入如下記號：rev(s)——將字符串s反過來寫，DAWG(s)——這是由字符串s建立的后綴自動機，ST(s)——這是s的后綴樹。

? ?我們介紹“擴展指針”的概念：對于樹節點v和字符c，ext[c,v]指向樹中對應于字符串c+v的節點（如果路徑c+v在某邊的終點結束，那就將其指向該

邊的較低點）；如果這樣一條路徑c+v不在樹中，那么擴展指針未定義。在某種意義上，擴展指針的對立面就是后綴鏈接。

?

定理1.DAWG(s)中后綴鏈接組成的樹就是后綴樹ST(rev(s))。

?

定理2.圖DAWG(s)的邊都能用后綴樹ST(rev(s))的擴展指針表示。另外，DAWG(s)中的連續轉移就是ST(rev(s))中反向的后綴指針。

?

這兩條定理允許使用兩個數據結構之一在O(n)的時間內構建另外一個——這兩個簡單的算法將在下面定理3,4討論。

? ?出于說明需要，我們下面展示一個包含后綴鏈接的后綴自動機的例子，以及其倒序字符串的相應后綴樹。例如，令字符

串s="abcbc"。

? ?DAWG("abcbc")（出于簡便我們在每個狀態上標出其識別的最長串）：

ST("cbcba")：

引理.

對任意兩個子串u和w，如下三個陳述是等價的：

·????????在字符串s中endpos(u)=endpos(w)

·????????在字符串rev(s)中firstpos(rev(u))=firstpos(rev(w))

·????????在后綴樹ST(rev(s))中，rev(u)和rev(w)匹配從根開始的一段相同路徑。

證明十分顯然：如果兩個字符串的起始位置集合相同，那么一個字符串只作為另外一個的前綴出現，這意味著在后綴樹中，二者之

間并沒有其他節點。

?因此，后綴自動機中的狀態和后綴樹中的節點一一對應。

?

定理1的證明.

?后綴自動機中的狀態和后綴樹中的節點一一對應.

?

考慮任意后綴鏈接y=link(x)。根據后綴鏈接的定義，longest(y)是longest(x)的一個后綴，并且y是所有滿足條件（和x的終點集合不同）

的狀態中使len(y)最大者。

?在rev(s)中，這意味著link(x)指向x所對應字符串的最長前綴，該前綴對應一個不同的狀態y。換句話說，后綴鏈接link(x)指向后綴樹中節

點x的父親。

?

定理2的證明.

?

后綴自動機中的狀態和后綴樹中的節點一一對應。

?

考慮后綴自動機DAWG(s)中的任意轉移(x,y,c)。這意味著y是包含子串longest(x)+c的終點集合等價類。對于rev(s)，y對應了一個子串，

該子串的firstpos（在文本rev(s)中）和c+rev(longest(x))的firstpos相同。

?這意味著：

rev(longest(y))=ext[c,rev(longest(x))].

（注：這里的用法并不嚴謹……請自行把字符串和節點對應）?

也就是該定理的第一部分，我們還需要證明第二部分：自動機中的所有連續轉移對應樹中的后綴指針。對于連續轉移，有length(y)=length(x)+1，

即在標識字符c后我們到達了一個狀態，它是一個不同的等價類。這意味著在rev(s)的后綴樹中，x節點對應的字符串恰好是y節點所對應字符串的，長

度比它小1的后綴——也就是說，后綴樹中y的后綴指針指向x，(x,y)就是樹中的反向后綴指針。

?

定理得證。

?

定理3.

使用后綴自動機DAWG(s)，我們可以用O(n)的時間構建后綴樹ST(rev(s))。

?

定理4.

使用后綴樹ST(rev(s))，我們可以用O(n)的時間構建后綴自動機DAWG(s)。

?

定理3的證明.

后綴樹ST(rev(s))的節點和DAWG(s)中的狀態一一對應。樹中與自動機中狀態v相對應的節點表示一個長度為len(v)的字符串。

根據定理1，ST(rev(s))中的邊恰好是把DAWG(s)的后綴鏈接反向，而邊的標記可以借助不同狀態的len計算（譯者注：從葉子開始，利用自動

機中狀態的len值計算后綴樹中的節點對應于哪個子串），或者更方便地，對自動機中每個狀態我們都能知道其endpos集合中的一個元素（在構建

后綴自動機時維護）。

?至于樹中的后綴指針，我們可以基于定理2構建：查找自動機中所有的連續轉移，對所有這樣的轉移(x,y)我們都在樹中添加一個后綴指針link[y]=x。

?因此，在O(n)時間內我們就可以構建一棵后綴樹及其中的后綴指針。

?（如果我們認為字母表的大小k并非常數，那么重建操作將花費O(n*logk)的時間。）

?

定理4的證明.

后綴自動機DAWG(s)包含的狀態和ST(rev(s))中的節點一一對應。對每個狀態v，其對應的最長字符串longest(v)都和后綴樹中從根到v的路徑翻轉后

形成的字符串相同。

?

根據定理2，為了構建自動機中的所有轉移，我們需要找到所有擴展ext[c,v]的指針。

?首先，注意到其中的一些指針直接由樹中的后綴指針得到。事實上，如果對于樹中任意節點x，我們考慮其后綴指針y=link[x]，那就意味著自動機中

有一個從y指向x的連續轉移，標記為樹節點x所對應字符串的第一個字符。

?不過，只是這樣我們并不能找到所有的擴展。額外地，有必要從葉子到根遍歷后綴樹，而且對于每個節點v都遍歷其所有兒子，對每個兒子觀察所有

擴展指針ext[c,w]，如果該指針上的字符c在節點v中還未發現，就將其復制到v中：

ext[c,v]=ext[c,w]，如果ext[c,w]=nil.

這一過程將在O(n)時間內完成，如果我們認為字母表的大小是常數。

最終，還需要建立后綴自動機中的后綴鏈接。而根據定理1，后綴鏈接可以直接由后綴樹ST(rev(s))的邊獲得。

這樣，我們就得到使用從倒序字符串的后綴樹建立后綴指針的O(n)算法。

?（不過，若字母表的大小k是變量，那么漸進復雜度就是O(n*logk)）。

?

在解決問題中的應用

下面看在后綴自動機的幫助下我們能做什么。

?

簡便起見，我們假設字母表的大小k為常數。

?

存在性查詢

問題.給定文本T，詢問格式如下：給定字符串P，問P是否是T的子串。?

復雜度要求.預處理O(length(T))，每次詢問O(P)。

?

算法.我們對文本T用O(length(T))建立后綴自動機。

現在回答單次詢問。假設狀態——變量v，最初是初始狀態T_0.我們沿字符串P給出的路徑走，因此從當前狀態經轉移來到新的狀態v

。如果在某時刻，當前狀態沒有要求字符的轉移，那么答案就是"no"。如果我們處理了整個字符串P，答案就是"yes"。

顯然這一算法將在時間O(length(P))內運行完畢。并且，該算法實際上找出了P在文本中出現過的最長前綴——如果模式串使得這些前綴

都很短，算法將比處理全部模式串要快得多。

?

不同的子串個數

問題.給定字符串S，問它有多少不同的子串。

?復雜度要求.O(length(S))。

?

算法.我們將字符串S建立后綴自動機。

?在后綴自動機中，S的任意子串都對應自動機中的一條路徑。答案就是從初始節點t_0開始，自動機中不同的路徑條數。

?已知后綴自動機是一張有向無環圖，我們可以考慮用動態規劃計算不同的路徑數量。

? 也就是，令d[v]為從狀態v開始的不同路徑條數（包括長度為零的路徑），則有轉移：

即d[v]是v所有后繼節點的d值之和加上1.

最終答案就是d[t_0]-1（減一以忽略空串）。

不同子串的總長

問題.給定字符串S，求其所有不同子串的總長度。

復雜度要求.O(length(S)).

?

算法.這一問題的答案和上一題類似，但現在我們必須考慮兩個狀態：不同子串的個數d[v]和它們的總長ans[v].

? ?上一題已描述了d[v]的計算方法，而ans[v]的計算方法如下：

即取所有后繼節點w的ans值，并將它和d[w]相加。因為這是每個字符串的首字母。

?

字典序第k小子串

問題.給定字符串S，一系列詢問——給出整數K_i，計算S的所有子串排序后的第K_i個。

復雜度要求.單次詢問O(length(ans)*Alphabet)，其中ans是該詢問的答案，Alphabet是字母表大小。

?算法.這一問題的基礎思路和上兩題類似。字典序第k小子串——自動機中字典序第k小的路徑。因此，考慮從每個狀態出

發的不同路徑數，我們將得以輕松地確定第k小路徑，從初始狀態開始逐位確定答案。

?

最小循環移位

問題.給定字符串S，找到和它循環同構的字典序最小字符串。

?復雜度要求.O(length(S)).

?

算法.我們將字符串S+S建立后綴自動機。該自動機將包含和S循環同構的所有字符串。

?從而，問題就簡化成了在自動機中找出字典序最小的，長度為length(S)的路徑，這很簡單：從初始狀態開始，每一步都貪心地走

，經過最小的轉移。

?

出現次數查詢

問題.給定文本T，詢問格式如下：給定字符串P，希望找出P作為子串在文本T中出現了多少次（出現區間可以相交）。

?復雜度要求.預處理O(length(T))，單次詢問O(length(P)).

?

算法.我們將文本T建立后綴自動機。

?然后我們需要進行預處理：對自動機中的每個狀態v都計算cnt[v]，等于其endpos(v)集合的大小。事實上，所有在T中對應同一狀態的

字符串都在T中出現了相同次數，該次數等于endpos中的位置數。

?不過，我們無法對所有狀態明確記錄endpos集合，所以我們只計算其大小cnt.

?為了實現這一點，如下處理。對每個狀態，如果它不是由“拷貝”而來，最初就賦值cnt=1.然后我們按長度len降序遍歷所有序列，并將

當前的cnt[v]加給后綴鏈接：

?cnt[link(v)]+=cnt[v].

? 你可能會說我們并沒有對每個狀態計算出了正確的cnt值。

?為什么這是對的？不經“拷貝”而來的狀態恰好有length(S)個，而且其中的第i個是我們添加第i個字符時得到的。因此，最初這些狀態的cnt=1，

其他狀態的cnt=0.

?然后我們對每個狀態v執行如下操作：cnt[link(v)]+=cnt[v].其意義在于，如果某字符串對應狀態v，曾在cnt[v]中出現過，那么它的所有后綴都

同樣在其中出現。

?這樣，我們就掌握了如何對自動機中所有狀態計算cnt值的方法。

?在此之后，詢問的答案就變得平凡——只需要返回cnt[t]，其中t是模式串P所對應的狀態。

?

首次出現位置查詢

問題.給定文本T，詢問格式如下：給定字符串P，求P在文本中第一次出現的位置。

?復雜度要求.預處理O(length(T))，單次詢問O(length(P)).

?

算法.對文本T建立后綴自動機。

?為了解決這一問題，我們需要預處理firstpos，找到自動機中所有狀態的出現位置，即，對每個狀態v我們希望找到一個位置firstpos[v]，代表

其第一次出現的位置。換句話說，我們希望預先找出每個endpos(v)中的最小元素（我們無法明確記錄整個endpos集合）。

? 維護這些firstpos的最簡單方法是在構建自動機時一并計算，當我們創建新的狀態cur時，一旦進入函數sa_extend()，就確定該值：

?firstpos(cur)=len(cur)-1（如果我們的下標從0開始）。

當拷貝節點q時，令：

?firstpos(clone)=firstpos(q)，（因為只有一個別的可能值——firstpos(cur)，顯然更大）。

?這樣就得到了查詢的答案——firstpos(t)-length(P)+1，其中t是模式串P對應的狀態。

?

所有出現位置查詢

問題.給定文本T，詢問格式如下：給定字符串P，要求給出P在T中的所有出現位置（出現區間可以相交）。

復雜度要求.預處理O(length(T))。單次詢問O(length(P)+answer(P))，其中answer(P)是答案集合的大小，即，要求時間復雜度和輸入輸出同階。

?

算法.對文本T建立后綴自動機，和上一個問題相似，在構建自動機的過程中對每個狀態計算第一次出現的終點firstpos。

?

假設我們收到了一個詢問——字符串P。我們找到了它對應的狀態t。

?顯然應當返回firstpos(t)。還有哪些位置？我們考慮自動機中那些包含了字符串P的狀態，即那些P是其后綴的狀態。

?換言之，我們需要找出所有能通過后綴鏈接到達狀態t的狀態。

?因此，為了解決這一問題，我們需要對每個節點儲存指向它的所有后綴鏈接。為了找到答案，我們需要沿著這些翻轉的后綴鏈接進行DFS/BFS，從狀

態t開始。

?這一遍歷將在O(answer(P))時間內結束，因為我們不會訪問同一狀態兩次（因為每個狀態的后綴鏈接僅指向一個點，因此不可能有兩條路徑通往同一

狀態）。

?然而，兩個狀態的firstpos值可能會相同，如果一個狀態是由另一個拷貝而來。但這不會影響漸進復雜度，因為每個非拷貝得到的節點只會有一個拷貝。

?此外，你可以輕松地除去那些重復的位置，如果我們不考慮那些拷貝得來的狀態的firstpos。事實上，所有拷貝得來的狀態都被其“母本”狀態的后綴鏈接

指向。因此，我們對每個節點記錄標簽is_clon，我們不考慮那些is_clon=true的狀態的firstpos。這樣我們就得到了answer(P)個不重復地狀態。

?給出一個離線版本的實現：

[cpp]?view plaincopy

1. struct?state?{??
2. ????...??
3. ????bool?is_clon;??
4. ????int?first_pos;??
5. ????vector<int>?inv_link;??
6. ????};??
7. ??????
8. ???????
9. ...?后綴自動機構建完畢?...??
10. for?(int?v=1;?v<sz;?++v)??
11. ????st[st[v].link].inv_link.push_back?(v);??
12. ...??
13. ????
14. ???
15. //?回答詢問--返回所有的出現位置（出現區間可能有重疊）??
16. void?output_all_occurences?(int?v,?int?P_length)?{??
17. ???if?(!?st[v].is_clon)??
18. ????????cout?<<?st[v].first_pos?-?P_length?+?1?<<?endl;??
19. ???for?(size_t?i=0;?i<st[v].inv_link.size();?++i)??
20. ????????output_all_occurences?(st[v].inv_link[i],?P_length);??
21. }??

查詢不在文本中出現的最短字符串

問題.給定字符串S和字母表。要求找出一個長度最短的字符串，使得它不是S的子串。

復雜度要求.O(length(S)).

?算法.在字符串S的后綴自動機上進行動態規劃。

?令d[v]為節點v的答案，即，我們已經輸入了字符串的一部分，匹配到v，我們希望找出有待添加的最少字符數量，以到達一個不存在的轉移。

?計算d[v]非常簡單。如果在v處某個轉移不存在，那么d[v]=1：用這個字符來“跳出”自動機，以得到所求字符串。

?否則，一個字符串無法達到要求，因此我們必須取所有字符中的最小答案：

原問題的答案等于d[t_0]，而所求字符串可以用記錄轉移路徑的方法得到。

?

求兩個字符串的最長公共子串

問題.給定兩個字符串S和T。要求找出它們的最長公共子串，即一個字符串X，它同時是S和T的子串。

? ?復雜度要求.O(length(S)+length(T)).

?

算法.我們對字符串S建立后綴自動機。

?

我們按照字符串T在自動機上走，查找它每個前綴在S中出現過的最長后綴。換句話說，對字符串T中的每個位置，我們都想找出S和T在該位置結束的最長公共子串。

?

為了實現這一點，我們定義兩個變量：當前狀態v和當前長度l。這兩個變量描述了當前的匹配部分：其長度和狀態，對應哪個字符串（如果不儲存長度就無法確定這一點，因為一個狀態可能匹配多個有不同長度的字符串）。

?

最初，p=t_0,l=0，即，匹配部分為空。

?

現在我們考慮字符T[i]，我們希望找到這個位置的答案。

·????????如果自動機中的狀態v有一個符號T[i]的轉移，我們可以簡單地走這個轉移，然后將長度l加一。

·????????如果狀態v沒有該轉移，我們應當嘗試縮短當前匹配部分，為此應當沿著后綴鏈接走：
v=link(v).
在此情況下，當前匹配長度必須被減少，但留下的部分盡可能多。顯然，應令l=len(v)：
l=len(v).
若新到達的狀態仍然沒有我們想要的轉移，那我們必須再次沿著后綴鏈接走，并且減少l的值，直到我們找到一個轉移（那就返回第一步），或者我們最終到達了空狀態-1（這意味著字符T[i]并未在S中出現，所以令v=l=0然后繼續處理下一個i）。

原問題的答案就是l曾經達到的最大值。

?

這種遍歷方法的漸進復雜度是O(length(T))，因為在一次移動中我們要么將l加一，要么沿著后綴鏈接走了若干次，每次都會嚴格減少l。因此，l總共的減少值之和不可能超過length(T)，這意味著線性時間復雜度。

?

代碼實現：

[cpp]?view plaincopy

1. string?lcs?(string?s,?string?t)?{??
2. ????sa_init();??
3. ????for?(int?i=0;?i<(int)s.length();?++i)??
4. ????????sa_extend?(s[i]);??
5. ??????
6. ????int?v?=?0,??l?=?0,??
7. ????????best?=?0,??bestpos?=?0;??
8. ????for?(int?i=0;?i<(int)t.length();?++i)?{??
9. ????????while?(v?&&?!?st[v].next.count(t[i]))?{??
10. ????????????v?=?st[v].link;??
11. ????????????l?=?st[v].length;??
12. ????????}??
13. ????????if?(st[v].next.count(t[i]))?{??
14. ????????v?=?st[v].next[t[i]];??
15. ?????????++l;??
16. ????????}??
17. ????????if?(l?>?best)??
18. ????????????best?=?l,??bestpos?=?i;??
19. ????}??
20. ????return?t.substr?(bestpos-best+1,?best);??
21. }??

多個字符串的最長公共子串

問題.給出K個字符串S_1~S_K。要求找出它們的最長公共子串，即一個字符串X，它是所有S_i的子串。

? ?復雜度要求.O(∑length(S_I)*K).

?

算法.將所有S_i連接在一起成為一個新的字符串T，其中每個S_i后要加上一個不同的分隔符D_i（即加上K個額外的不同特殊字符D_1~D_K）：

我們對字符串T構建后綴自動機。

?現在我們需要在后綴自動機找出一個字符串，它是所有字符串S_i的子串。注意到如果一個子串在某個字符串S_j中出現過，那么后綴自動機中存在一

條以這個子串為前綴的路徑，包含分隔符D_j，但不包含其他分隔符D_1,...,D_j-1,D_j+1,...,D_k。

?因此，我們需要計算“可達性”：對自動機中的每個狀態和每個字符D_i，計算是否有一條從該狀態開始的路徑，包含分隔符D_i，但不包含別的分隔符。

很容易用DFS/BFS或者動態規劃實現。在此之后，原問題的答案就是字符串longest(v)，其中v能夠到達所有的分隔符。

?

OJ上的題目

可以用后綴自動機解決的題目：

SPOJ#7258 SUBLEX"Lexicographical Substring Search"

BZOJ#2555 Substring

SPOJ#8222 NSUBSTR"Substrings"

SPOJ#1812 LCS2"Longest Common Substrings?II"

BZOJ#3998 弦論

參考文獻

我們首先給出和后綴自動機有關的一些第一手研究：

·????????A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R.McConnell.Linear Size Finite Automata for the Set of All Subwordsof a Word. An Outline of Results?[1983]

·????????A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler.The SmallestAutomaton Recognizing the Subwords of a Text[1984]

·????????Maxime Crochemore.?OptimalFactor Transducers?[1985]

·????????Maxime Crochemore.?Transducersand Repetitions?[1986]

·????????A. Nerode.?Linear automatontransformations?[1958]

此外，還有一些當代資源，這一主題在許多有關字符串算法的書籍中被提到：

·????????Maxime Crochemore, Wowjcieh Rytter.?Jewels ofStringology?[2002]

·????????Bill Smyth.?Computing Patterns in Strings?[2003]

·????????Билл Смит.?Методы и алгоритмы вычислений на строках?[2006]

總結

以上是生活随笔為你收集整理的后缀自动机详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。