后綴自動機suffixautomaton-leanoteleanote,

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

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

3、POJ太慢了,新的算法,OI中使用的字符串處理工具,Suffix Array 后綴數(shù)組 Suffix Tree 后綴樹Aho-Corasick Automaton AC自動機Hash 哈希,Suffix Automaton又是什么呢？,什么是自動機,有限狀態(tài)自動機的功能是識別字符串，令一個自動機A，若它能識別字符串S，就記為A(S)=True，否則A(S)=False。自動機由五個部分組成，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)這個轉(zhuǎn)移不存在，為了方便，不妨設(shè)其為null，同時null只能轉(zhuǎn)移到null。null表示不存在的狀態(tài)。同時令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,,,后綴自動機的定義,給定字符串SS的后綴自動機suffix automaton(以后簡記為SAM)是一個能夠識別S的所有后綴的自動機。即SAM(x) = True，當(dāng)且僅當(dāng)x是S的后綴同時后面可以看出，后綴自動機也能用來識別S所有的子串。,最簡單的實現(xiàn),考慮字符串”aabbabd”,我們可以講該字符串的

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

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

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

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

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

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

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

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

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

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

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

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

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

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