后綴自動(dòng)機(jī)學(xué)習(xí)

實(shí)用文檔后綴自動(dòng)機(jī)實(shí)質(zhì)上是字母樹,記錄的字符串是某個(gè)字符串s的所有后綴.這里以字符串ACADD為例:這樣很浪費(fèi)空間和時(shí)間(實(shí)際上都是O(n^2)).但是,注意:這棵字母樹的結(jié)點(diǎn)雖然多,但大部分結(jié)點(diǎn)都只有一個(gè)兒子,而且有很多段是一樣的.那么,利用公共部分,就可以對(duì)空間進(jìn)行壓縮,具體地說,就是把自己連到兒子的邊刪掉(并把該兒子及其后代刪掉),再把這條邊連到別的子樹,這樣就能充分利用公共部分,節(jié)省空間.但是,如何保證這樣做和原來的笨做法是等價(jià)的,又如何把時(shí)間復(fù)雜度和空間復(fù)雜度降到O(n)?這是個(gè)問題.幸運(yùn)的是,后綴自動(dòng)機(jī)出現(xiàn)了.后綴自動(dòng)機(jī)是這樣的:在后綴自動(dòng)機(jī)中,為了節(jié)省空間,某個(gè)點(diǎn)有可能成為多個(gè)結(jié)點(diǎn)的兒子,可以保證在后綴自動(dòng)機(jī)中遍歷出來的所有字符串不會(huì)重復(fù),而且剛好是原串s的所有子串.先講講后綴自動(dòng)機(jī)的大致做法:假設(shè)當(dāng)前已經(jīng)建好了s的某個(gè)前綴的后綴自動(dòng)機(jī)t,那么就要通過某種算法,添加一個(gè)字符x,得到s另一前綴tx的后綴自動(dòng)機(jī),這樣每次插入一個(gè)字符,最后把s的所有字符按順序插入完畢就得到了s的后綴自動(dòng)機(jī).這樣的話,建造后綴自動(dòng)機(jī)的過程是在線的,就是說,可以任意時(shí)刻詢問s的某些信息,也可以任意時(shí)刻在s的結(jié)尾插入一些字符,變成新的字符串.不過,刪除是不支持的.在后綴自動(dòng)機(jī)中,每個(gè)結(jié)點(diǎn)儲(chǔ)存的信息有:son[26]:返回該結(jié)點(diǎn)對(duì)應(yīng)的子串加上某個(gè)字符后生成的合法子串在后綴自動(dòng)機(jī)中所對(duì)應(yīng)的位置(其實(shí)就和字母樹一樣),如果該指針不存在,就說明這樣的子串是不存在的(即不是s的子串)pre:注意這不是返回它的父結(jié)點(diǎn)(因?yàn)槟硞€(gè)點(diǎn)有可能成為多個(gè)結(jié)點(diǎn)的兒子),而是返回上一個(gè)可以接收后綴的結(jié)點(diǎn)(如果當(dāng)前結(jié)點(diǎn)可以接收新的后綴,那么pre指向的結(jié)點(diǎn)也一定可以接收后綴).step:返回的是從根結(jié)點(diǎn)走到該結(jié)點(diǎn),最多需要多少步.為了方便下面的敘述,這里先提出三個(gè)后綴自動(dòng)機(jī)的性質(zhì):①從root到任意結(jié)點(diǎn)p的每條路徑上的字符組成的字符串,都是當(dāng)前串t的子串.②因?yàn)闈M足性質(zhì)一,所以如果當(dāng)前結(jié)點(diǎn)p是可以接收新后綴的結(jié)點(diǎn),那么從root到任意結(jié)點(diǎn)p的每條路徑上的字符組成的字符串,都是必定是當(dāng)前串t的后綴.③如果結(jié)點(diǎn)p可以接收新的后綴,那么p的pre指向的結(jié)點(diǎn)也可以接收后綴,反過來就不行.下面的敘述中,將直接應(yīng)用這兩個(gè)性質(zhì).當(dāng)前建立的后綴自動(dòng)機(jī)是對(duì)應(yīng)字符串t的,現(xiàn)在要插入字符x,把t的后綴自動(dòng)機(jī)變成tx的后綴自動(dòng)機(jī).首先建立儲(chǔ)存當(dāng)前字符x的結(jié)點(diǎn)np,找到之前最后一個(gè)建立的結(jié)點(diǎn)(因?yàn)樗欢M足性質(zhì)②),然后就不斷按pre指針跳(直到跳到有x兒子的結(jié)點(diǎn)為止).假設(shè)當(dāng)前跳到p結(jié)點(diǎn),如果p沒有x兒子,那么它一定可以接收新來的字符,然后就把p的x兒子賦值為np(這時(shí),p接收了后綴字符x,目前已經(jīng)不可以接收新的后綴字符了).然后,就要處理有x兒子的結(jié)點(diǎn)了,假設(shè)p的x兒子是q.只有2種情況:①step[q]=step[p]+1.因?yàn)槲覀円缶Y自動(dòng)機(jī)的結(jié)點(diǎn)盡量少,所以要盡量共用一些信息.這是對(duì)應(yīng)的圖:這時(shí),p點(diǎn)是滿足性質(zhì)②的.這時(shí),如果可以把np直接接到p后面,就可以省下很多空間了,但是因?yàn)閝點(diǎn)的存在,np不能直接接到p后面,否則p-q的信息就丟失了.那么能不能把q當(dāng)成np呢?就是說q可不可以像np那樣,作為t的”最后一個(gè)字符”,來接收新的后綴呢?答案是肯定的.但p可以接收新的后綴,q就不一定能接收新的后綴,這樣做會(huì)不會(huì)有問題?本來,這樣的做法是不行的(這是情況②要解決的問題),但step[q]=step[p]+1,保證了:q原本是從p的路徑上來的,而且p和q之間不會(huì)夾雜其它字符.雖然q本來不一定可以接收新的后綴,但p可以接收后綴x,如果當(dāng)前經(jīng)過p來到q,就可以視為是在t的某個(gè)后綴后面插入了x(現(xiàn)在q就是那個(gè)x),并且在下一次插入的時(shí)候,q也可以接收后綴(因?yàn)樗F(xiàn)在可以被視為x的結(jié)點(diǎn)了),所以就把np的pre指向q.在這里,我有個(gè)原來不懂的地方(后來明白了):因?yàn)閝當(dāng)前不一定是可以接收后綴的點(diǎn),現(xiàn)在把它當(dāng)成了代表x的結(jié)點(diǎn)并已經(jīng)將它變成可以接收新后綴的狀態(tài).這對(duì)于來到p結(jié)點(diǎn)后再走q結(jié)點(diǎn)的路徑必然是對(duì)的(因?yàn)閬淼絧結(jié)點(diǎn),就相當(dāng)于找到了t的一個(gè)后綴,現(xiàn)在又找到q結(jié)點(diǎn),就相當(dāng)于找到一個(gè)tx的后綴了),但是如果遍歷的時(shí)候不經(jīng)過p就直接到了q,好像就不能保證所在路徑對(duì)應(yīng)的字符串是tx的后綴了,這時(shí)它還能接收新的后綴嗎?其實(shí),step[q]=step[p]+1就保證了經(jīng)過q,就一定會(huì)經(jīng)過p;而如果不經(jīng)過p,就只能從root直接來了.也就是說,保證了到達(dá)p的都是后綴.為什么?可以用反證法(我想了1個(gè)多鐘啊):假設(shè)原命題不成立,那么就有兩種可能:一.當(dāng)前的x字符,之前沒有出現(xiàn)過.這樣的話,有x字符的子串必然是后綴,與假設(shè)矛盾.二.當(dāng)前的x字符,之前已經(jīng)出現(xiàn)過.這樣的話,有x字符而不是后綴的子串必然與之前的某個(gè)代表字符x的結(jié)點(diǎn)連接,而不是與當(dāng)前的q點(diǎn)連接,否則后綴自動(dòng)機(jī)的性質(zhì)早就被破壞了,故也與假設(shè)矛盾.綜上,step[q]=step[p]+1,保證了到達(dá)p的都是后綴.同時(shí)這也解釋了為什么要找最靠后的一個(gè)有x兒子的結(jié)點(diǎn)了.于是,我們就把代表t的后綴自動(dòng)機(jī)改進(jìn)為代表tx的后綴自動(dòng)機(jī)了.如圖(實(shí)邊是son指針,虛邊是pre指針):②step[q]>step[p]+1這和上一種情況一樣,也面臨著q點(diǎn)是否可以當(dāng)成x結(jié)點(diǎn)的問題.在上一種情況的描述中,我們可以知道,step[q]=step[p]+1可以保證q原本是從p的路徑上來的,而且p和q之間不會(huì)夾雜其它字符,所以可以直接把q結(jié)點(diǎn)當(dāng)成x結(jié)點(diǎn).那么反過來,step[q]>step[p]+1,就說明p和q之間有可能會(huì)夾雜其它字符,這就不能保證把q當(dāng)成x結(jié)點(diǎn)以后,到q的路徑都是tx的后綴了,于是我們不能采取和前一種情況一樣的做法.但是,我們可以模仿前一種情況的做法.上面的做法合法,是因?yàn)閟tep[q]=step[p]+1,那么如果新建一個(gè)結(jié)點(diǎn)nq來代替q,同時(shí)保證step[nq]=step[p]+1就相當(dāng)于第一種情況了,這時(shí),只要把q的son邊和pre邊都copy到nq上即可.但是別忘了把nq的pre改為p,再把nq和np的pre都改為nq.因?yàn)楝F(xiàn)在nq代替了q,所以np的pre是nq.由性質(zhì)③可知nq的pre只能是p.同樣的,q和nq也滿足性質(zhì)③,所以q的pre只能是nq.最后,還要再按p的pre指針往上跳,把son[x]=q的p結(jié)點(diǎn)改為son[x]=nq(因?yàn)閚q代替了q).先貼個(gè)程序:structsuffix_automaton{

strings;

intson[maxn][26],pre[maxn],step[maxn],last,total;

inlinevoidpush_back(intv)

{

step[++total]=v;

}

voidExtend(charch)

{

push_back(step[last]+1);

intp=last,np=total;

for(;!son[p][ch];p=pre[p])son[p][ch]=np;

if(!p)pre[np]=0;

else

{

intq=son[p][ch];

if(step[q]!=step[p]+1)

{

push_back(step[p]+1);

intnq=total;

memcpy(son[nq],son[q],sizeof(son[q]));

pre[nq]=pre[q];

pre[q]=pre[np]=nq;

for(;son[p][ch]==q;p=pre[p])son[p][ch]=nq;

}

elsepre[np]=q;

}

last=np;

}

voidBuild()

{

fin>>s;

total=last=0;

memset(son,0,sizeof(son));

memset(pre,0,sizeof(pre));

memset(step,0,sizeof(step));

for(inti=0,End=s.size();i!=End;i++)Extend(s[i]-'A');

visit(0,0);

}}suf;在外部調(diào)用suf.Build()即可.空間復(fù)雜度:很明顯,每次插入最多增加2個(gè)結(jié)點(diǎn),所以是O(n)的.時(shí)間復(fù)雜度:暫時(shí)還沒算好,但應(yīng)該是O(n)的.下面是ACADD的構(gòu)造過程(實(shí)邊是son指針,虛邊是pre指針):①插入A:A的上一個(gè)可以接收后綴的點(diǎn)只能是根結(jié)點(diǎn),所以A的pre指向root,step=1.②插入C:C的上一個(gè)可以接收后綴的點(diǎn)只能是根結(jié)點(diǎn),所以C的pre指向root,step=2.在pre指針跳躍的過程中,A和root都連了C了.③插入A:p指針先指向C結(jié)點(diǎn),然后再跳到root,現(xiàn)在root有A兒子,所以檢查root的step值是否等于root的A兒子的step值+1.現(xiàn)在判斷成功,所以root的A兒子現(xiàn)在有雙重身份(后綴“A”的最后一個(gè)字符,和后綴”ACA”的最后一個(gè)字符),現(xiàn)在是情況①,所以新建立的點(diǎn)的pre連到它即可.而且因?yàn)榈谝粋€(gè)A對(duì)于root來說,代替了第二個(gè)A,所以root不用往第二個(gè)A結(jié)點(diǎn)連邊.現(xiàn)在的后綴自動(dòng)機(jī)變成了這樣:④插入D:也是往上跳就行了,跳完兩個(gè)A結(jié)點(diǎn)就直接跳到根,都是情況①.完成后就多了3條實(shí)邊和一條虛邊.⑤插入D:首先確定p和q指針,step[q]<step[p]+1隨之確定這是第二種情況.然后建立新結(jié)點(diǎn)nq,把q的指針copy給nq,nq的pre改為p,q和np的pre改為nq.最后,p指針一邊往上跳,一邊把son[x]=q的p結(jié)點(diǎn)改為son[x]=nq.最后,后綴自動(dòng)機(jī)就誕生了:按字典序遍歷一遍:AACACAACADACADDAD