2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩56頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

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

6、所有后綴插入一個(gè)Trie中,就像右圖那樣。那么初始狀態(tài)就是根,狀態(tài)轉(zhuǎn)移函數(shù)就是這顆樹的邊,結(jié)束狀態(tài)集合就是所有的葉子。,,狀態(tài)數(shù)量太多了!怎么破?,最簡狀態(tài)后綴自動機(jī),顧名思義,就是狀態(tài)數(shù)最少的后綴自動機(jī),在后面可以證明它的大小是線性的,我們先來看一些性質(zhì)。假如我們得到了這個(gè)最簡狀態(tài)后綴自動機(jī)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ì),由于每個(gè)子串都必然包含在SAM的某個(gè)狀態(tài)里。那么一個(gè)字符串s是S的子串,當(dāng)且僅當(dāng),ST(s)!=null那么我們就可以用SAM來解決子串判定問題。同時(shí)也可以求出這個(gè)子串的出現(xiàn)個(gè)數(shù),就是所在狀態(tài)Right集合的大小。,關(guān)于子串的性質(zhì),在一個(gè)狀態(tài)中直接保存Right集合會消耗過多的空間,我們可以發(fā)現(xiàn)狀態(tài)的Right就

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

9、法實(shí)現(xiàn)相比后綴樹來說要簡單很多,盡管可能不是非常好理解。讓我們先回顧一下性質(zhì),定義和性質(zhì)的回顧,狀態(tài)s,轉(zhuǎn)移trans,初始狀態(tài)init,結(jié)束狀態(tài)集合end。母串S,S的后綴自動機(jī)SAM(Suffix Automaton的縮寫)。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è)樹形結(jié)構(gòu)。不妨叫它Parent樹。,定義的回顧,一個(gè)Right集合和一個(gè)長度定義了一個(gè)子串。對于狀態(tài)s,使得Right(s)合法的子串長度是一個(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ā)沒有標(biāo)號為ch的邊,,定義的

11、回顧,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,,每個(gè)階段,接下來考慮節(jié)點(diǎn)nq,在轉(zhuǎn)移的過程中,結(jié)束位置L+1是不起作用的,所以trans(nq)就跟原來的trans(q)是一樣的,拷貝即可。,每個(gè)階段,,每個(gè)階段,自此我們圓滿的解決了轉(zhuǎn)移的問題。嘟嘟嚕,搞完啦~~,每個(gè)階段:回顧,,每個(gè)階段:回顧,否則新建節(jié)點(diǎn)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++的代碼實(shí)現(xiàn),C++的代碼實(shí)現(xiàn),雖然我講了這么多代碼還是很好寫的,,,讓我們實(shí)戰(zhàn)一下吧實(shí)踐出真知!實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)!,I.最小循環(huán)串,給一個(gè)字符串S,每次可以將它的第一個(gè)字符移到最后面,求這樣能得到的字典序最小的字符串。如BBAAB,最小的就是AABBB考慮字符

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

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

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

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

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,同時(shí)最大匹配長度為len我們讀入字符x。如果s有標(biāo)號為x的邊,那么s=trans(s,x),len = len+1否則我們找到s的第一個(gè)祖先a,它有標(biāo)號為x的邊,令s=trans(a,x),len=Max(a)+1。如果沒有這樣的祖先,那么令s=root,len=0。在過程中更新狀態(tài)的最大匹配長度,V:SPOJ LCS,注意到我們求的是對于任意一個(gè)Right集合中的r,最大的匹配長度

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論