后綴自動(dòng)機(jī)suffixautomaton-leanoteleanote,

1、后綴自動(dòng)機(jī)Suffix Automaton,杭州外國(guó)語(yǔ)學(xué)校 陳立杰WJMZBMR,吐槽&回答,Q：你是哪里的弱菜？我聽(tīng)都沒(méi)聽(tīng)說(shuō)過(guò)！A：我是來(lái)自杭州外國(guó)語(yǔ)學(xué)校的陳立杰，確實(shí)是弱菜。Q：Suffix Automaton？我根本就沒(méi)有聽(tīng)說(shuō)過(guò)這種數(shù)據(jù)結(jié)構(gòu)。A：這個(gè)還是有點(diǎn)用處的，等下我會(huì)講的，你就當(dāng)長(zhǎng)知識(shí)了吧。Q：呼嚕嚕~~~~~~A：睡好。。。,先讓我們看SPOJ上的一道題目,1812. Longest Common

2、 Substring II題目大意：給出N(N <= 10)個(gè)長(zhǎng)度不超過(guò)100000的字符串，求他們的最長(zhǎng)公共連續(xù)子串。時(shí)限：SPOJ上的2s,一個(gè)簡(jiǎn)單的做法,二分答案之后使用哈希就可以在O(LlogL)的時(shí)間內(nèi)解決這個(gè)問(wèn)題。這個(gè)做法非常經(jīng)典就不詳細(xì)講了。,看起來(lái)很簡(jiǎn)單。。但是。。。,我們可以看到大部分人都TLE了。。為什么呢？,SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了SPOJ太慢了S

3、POJ太慢了,新的算法,OI中使用的字符串處理工具,Suffix Array 后綴數(shù)組 Suffix Tree 后綴樹(shù)Aho-Corasick Automaton AC自動(dòng)機(jī)Hash 哈希,Suffix Automaton又是什么呢？,什么是自動(dòng)機(jī),有限狀態(tài)自動(dòng)機(jī)的功能是識(shí)別字符串，令一個(gè)自動(dòng)機(jī)A，若它能識(shí)別字符串S，就記為A(S)=True，否則A(S)=False。自動(dòng)機(jī)由五個(gè)部分組成，alpha：字符集，state：狀態(tài)集

4、合，init：初始狀態(tài)，end：結(jié)束狀態(tài)集合，trans：狀態(tài)轉(zhuǎn)移函數(shù)。不妨令trans(s,ch)表示當(dāng)前狀態(tài)是s，在讀入字符ch之后，所到達(dá)的狀態(tài)。如果trans(s,ch)這個(gè)轉(zhuǎn)移不存在，為了方便，不妨設(shè)其為null，同時(shí)null只能轉(zhuǎn)移到null。null表示不存在的狀態(tài)。同時(shí)令trans(s,str)表示當(dāng)前狀態(tài)是s，在讀入字符串str之后，所到達(dá)的狀態(tài)。,trans(s,str),Cur = s;For i =

5、0 to Length(str)-1Cur = trans(Cur,str[i]);trans(s,str) 就是Cur,,,后綴自動(dòng)機(jī)的定義,給定字符串SS的后綴自動(dòng)機(jī)suffix automaton(以后簡(jiǎn)記為SAM)是一個(gè)能夠識(shí)別S的所有后綴的自動(dòng)機(jī)。即SAM(x) = True，當(dāng)且僅當(dāng)x是S的后綴同時(shí)后面可以看出，后綴自動(dòng)機(jī)也能用來(lái)識(shí)別S所有的子串。,最簡(jiǎn)單的實(shí)現(xiàn),考慮字符串”aabbabd”,我們可以講該字符串的

6、所有后綴插入一個(gè)Trie中，就像右圖那樣。那么初始狀態(tài)就是根，狀態(tài)轉(zhuǎn)移函數(shù)就是這顆樹(shù)的邊，結(jié)束狀態(tài)集合就是所有的葉子。,,狀態(tài)數(shù)量太多了！怎么破？,最簡(jiǎn)狀態(tài)后綴自動(dòng)機(jī),顧名思義，就是狀態(tài)數(shù)最少的后綴自動(dòng)機(jī)，在后面可以證明它的大小是線性的，我們先來(lái)看一些性質(zhì)。假如我們得到了這個(gè)最簡(jiǎn)狀態(tài)后綴自動(dòng)機(jī)SAM。我們令ST(str)表示trans(init,str)。就是初始狀態(tài)開(kāi)始讀入字符串str之后，能到達(dá)的狀態(tài)。,分析,,分析,

7、,,分析,分析,,狀態(tài)數(shù)的線性證明,,狀態(tài)數(shù)的線性證明,狀態(tài)數(shù)的線性證明,,一些性質(zhì),,,一些性質(zhì),,關(guān)于子串的性質(zhì),由于每個(gè)子串都必然包含在SAM的某個(gè)狀態(tài)里。那么一個(gè)字符串s是S的子串，當(dāng)且僅當(dāng)，ST(s)!=null那么我們就可以用SAM來(lái)解決子串判定問(wèn)題。同時(shí)也可以求出這個(gè)子串的出現(xiàn)個(gè)數(shù)，就是所在狀態(tài)Right集合的大小。,關(guān)于子串的性質(zhì),在一個(gè)狀態(tài)中直接保存Right集合會(huì)消耗過(guò)多的空間，我們可以發(fā)現(xiàn)狀態(tài)的Right就

8、是它Parent樹(shù)中所有孩子Right集合的并集，進(jìn)一步的話，就是Parent樹(shù)中它所有后代中葉子節(jié)點(diǎn)的Right集合的并集。那么如果按dfs序排列，一個(gè)狀態(tài)的right集合就是一段連續(xù)的區(qū)間中的葉子節(jié)點(diǎn)的Right集合的并集，那么我們也就可以快速求出一個(gè)子串的所有出現(xiàn)位置了。樹(shù)的dfs序列：所有子樹(shù)中節(jié)點(diǎn)組成一個(gè)區(qū)間。,線性構(gòu)造算法,我們的構(gòu)造算法是Online的，也就是從左到右逐個(gè)添加字符串中的字符。依次構(gòu)造SAM。這個(gè)算

9、法實(shí)現(xiàn)相比后綴樹(shù)來(lái)說(shuō)要簡(jiǎn)單很多，盡管可能不是非常好理解。讓我們先回顧一下性質(zhì),定義和性質(zhì)的回顧,狀態(tài)s，轉(zhuǎn)移trans，初始狀態(tài)init，結(jié)束狀態(tài)集合end。母串S，S的后綴自動(dòng)機(jī)SAM(Suffix Automaton的縮寫(xiě))。Right(str)表示str在母串S中所有出現(xiàn)的結(jié)束位置集合。一個(gè)狀態(tài)s表示的所有子串Right集合相同,為Right(s)。Parent(s)表示使得Right(s)是Right(x)的真子集，

10、并且Right(x)的大小最小的狀態(tài)x。Parent函數(shù)可以表示一個(gè)樹(shù)形結(jié)構(gòu)。不妨叫它Parent樹(shù)。,定義的回顧,一個(gè)Right集合和一個(gè)長(zhǎng)度定義了一個(gè)子串。對(duì)于狀態(tài)s，使得Right(s)合法的子串長(zhǎng)度是一個(gè)區(qū)間，為|[Min(s),Max(s)]Max(Parent(s)) = Min(s)-1。SMA的狀態(tài)數(shù)量和邊的數(shù)量，都是O(N)的。不妨令trans(s,ch)==null表示從s出發(fā)沒(méi)有標(biāo)號(hào)為ch的邊，,定義的

11、回顧,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,接下來(lái)考慮節(jié)點(diǎn)nq,在轉(zhuǎn)移的過(guò)程中,結(jié)束位置L+1是不起作用的，所以trans(nq)就跟原來(lái)的trans(q)是一樣的，拷貝即可。,每個(gè)階段,,每個(gè)階段,自此我們圓滿(mǎn)的解決了轉(zhuǎn)移的問(wèn)題。嘟嘟嚕，搞完啦～～,每個(gè)階段：回顧,,每個(gè)階段：回顧,否則新建節(jié)點(diǎn)nq，trans(nq,*)=trans(q,*)Parent(nq) = Parent(q

12、) (先前的)Parent(q) = nqParent(np)=nq對(duì)所有trans(v,x) == q的p的祖先v，trans(v,x) 改成nq,C++的代碼實(shí)現(xiàn),C++的代碼實(shí)現(xiàn),雖然我講了這么多代碼還是很好寫(xiě)的,,,讓我們實(shí)戰(zhàn)一下吧實(shí)踐出真知！實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)！,I.最小循環(huán)串,給一個(gè)字符串S，每次可以將它的第一個(gè)字符移到最后面，求這樣能得到的字典序最小的字符串。如BBAAB，最小的就是AABBB考慮字符

13、串SS，我們就是要求SS的長(zhǎng)度為L(zhǎng)ength(S)且字典序最小的子串，那么我們構(gòu)造出SS的SAM，從init開(kāi)始每次走標(biāo)號(hào)最小的轉(zhuǎn)移，走Length(S)步即可以得到結(jié)果。為什么這樣是對(duì)的就留給大家作為小思考了。,II.SPOJ NSUBSTR,給一個(gè)字符串S，令F(x)表示S的所有長(zhǎng)度為x的子串中，出現(xiàn)次數(shù)的最大值。求F(1)..F(Length(S))Length(S) <= 250000我們構(gòu)造S的SAM，那么對(duì)于一

14、個(gè)節(jié)點(diǎn)s，它的長(zhǎng)度范圍是[Min(s),Max(s)]，同時(shí)他的出現(xiàn)次數(shù)是|Right(s)|。那么我們用|Right(s)|去更新F(Max(s))的值。同時(shí)最后從大到小依次用F(i)去更新F(i-1)即可。為什么這樣是對(duì)的也作為小思考。,III.BZOJ2555 SubString,你要維護(hù)一個(gè)串，支持在末尾添加一個(gè)字符和詢(xún)問(wèn)一個(gè)串在其中出現(xiàn)了多少次這兩個(gè)操作。必須在線。構(gòu)造串的SAM，每次在后面加入一個(gè)字符，可以注

15、意到真正影響答案的是Right集合的大小，我們需要知道一個(gè)狀態(tài)的Right集合有多大。,III.BZOJ2555 SubString,回顧構(gòu)造算法，對(duì)Parent的更改每個(gè)階段只有常數(shù)次，同時(shí)最后我們插入了狀態(tài)np，就將所有np的祖先的Right集合大小+了1。方法1：使用動(dòng)態(tài)樹(shù)維護(hù)Parent樹(shù)。方法2：使用平衡樹(shù)維護(hù)Parent樹(shù)的dfs序列。這兩種方法跟今天的主題無(wú)關(guān)，不詳細(xì)講了。,IV:SPOJ SUBLEX,給一個(gè)長(zhǎng)度不

16、超過(guò)90000的串S，每次詢(xún)問(wèn)它的所有不同子串中，字典序第K小的，詢(xún)問(wèn)不超過(guò)500個(gè)。我們可以構(gòu)造出S的SAM，同時(shí)預(yù)處理從每個(gè)節(jié)點(diǎn)出發(fā)，還有多少不同的子串可以到達(dá)。然后dfs一遍SAM，就可以回答詢(xún)問(wèn)了。具體實(shí)現(xiàn)作為小練習(xí)留給大家。,V:SPOJ LCS,給兩個(gè)長(zhǎng)度小于100000的字符串A和B，求出他們的最長(zhǎng)公共連續(xù)子串。我們構(gòu)造出A的后綴自動(dòng)機(jī)SAM對(duì)于SAM的每個(gè)狀態(tài)s，令r為Right(s)中任意的一個(gè)元素，它代

17、表的是結(jié)束位置在r的，長(zhǎng)度在[Min(s),Max(s)]之間的所有子串。AAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAArAAAAAAAAAAAAA我們不妨對(duì)狀態(tài)s，求出所有B的子串中，從任意r開(kāi)始往前能匹配的最大長(zhǎng)度L，那么min(L,Max(s))就可以更新答案了。,V:SPOJ LCS,我們考

18、慮用SAM讀入字符串B。令當(dāng)前狀態(tài)為s，同時(shí)最大匹配長(zhǎng)度為len我們讀入字符x。如果s有標(biāo)號(hào)為x的邊，那么s=trans(s,x),len = len+1否則我們找到s的第一個(gè)祖先a，它有標(biāo)號(hào)為x的邊，令s=trans(a,x),len=Max(a)+1。如果沒(méi)有這樣的祖先，那么令s=root,len=0。在過(guò)程中更新?tīng)顟B(tài)的最大匹配長(zhǎng)度,V:SPOJ LCS,注意到我們求的是對(duì)于任意一個(gè)Right集合中的r，最大的匹配長(zhǎng)度

19、。那么對(duì)于一個(gè)狀態(tài)s，它的結(jié)果自然也可以作為它Parent的結(jié)果，我們可以從底到上更新一遍。然后問(wèn)題就解決了。,VI:SPOJ LCS2,,一些其他的東西,其實(shí)不僅僅有Suffix Automaton還有。。Factor AutomatonSuffix OracleFactor OracleSuffix CactusOracle的意思是神諭！聽(tīng)起來(lái)很強(qiáng)吧。,Factor Oracle,一個(gè)串的Factor Oracle是一