當前位置:成語大全網 - 新華字典 - 後綴自動機如何限制串長

後綴自動機如何限制串長

後綴自動機是壹個有限狀態自動機,有限狀態自動機的功能是識別字符串。後綴自動機,可以識別壹個字符串的所有子串。

後綴自動機原理。我們考慮如果把壹個字符串的後綴建立壹棵字典樹,那麽其狀態和結點都是O(N^2)級別的。因為不能充分利用字符串本身的特點。我們考慮,假設我們有壹個字符串T,某個串s是其的子串,那麽我們在s後面加入壹些字符就有可能使其變成T的後綴,而如果串s不是T的子串,就沒有必要浪費空間。所以,為了識別所有的後綴,就要盡可能的利用這些可能。後綴自動機是最簡狀態自動機,其狀態數是線性的,可以證明。

我們按照壹定的順序來壹點壹點剖分自動機。

狀態。我們知道,後綴自動機是可以在線構建的。每插入壹個新的字符,在自動機中就會產生壹個新的狀態。我們用State(s)表示已經插入字符串s後所能達到的狀態。每個狀態裏面我們有這樣3個元素。 pre,其指向上壹個可以接收相同後綴的結點,我們不能把這個理解成為指向當前狀態的父親,因為壹個節點可能有許多個“父親”。 len,表示從根節點(空狀態,即為沒有插入任何壹個字符)走到當前點最多要走多少步,也可以理解為在當前狀態下自動機可以識別的最長後綴的長度。next[26],記錄s已經加入自動機後,再加入壹個字符後,該字符在自動機中的位置。

可以識別。我們說壹個狀態State可以識別某個字符串x,其意思表示為,在自動機中存在從根結點到當前的狀態的壹條路徑,使得串x是這條路徑形成的字符串的壹個子串。

Right集合,我們定義這樣壹個集合:其表示某壹狀態下所有能識別的後綴的右端點位置集合。

舉個例子,比如說對於這樣壹個串T = “aabaaabaaabbab”。可以識別“ab”的的Right集合 S1 = {3,7,11,13}。

在繼續向下之前,先提出壹個註意的地方,就是,當我們達到State(s)時,假設是第壹次達到,那麽此時的自動機是串s的自動機,而不是整個文本串T(s是其的壹個子串)的自動機。壹定要註意語句的主語。

Parent樹。我們先來對其進行壹個如下的分析。

首先對於壹個空串來說,其可識別的位置為所有位置(其實沒有必要,這麽說是為了壹會的圖畫方便些)。

Right(空) = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};

然後我們考慮長度為1的。

Right(“a”)={1,2,4,5,6,8,9,10,13},

Right("b") = {3, 7, 11, 12, 14}.

接下來, Right(“aa”) = {2, 5, 6, 9, 10}, Right(“ab”) = {3, 7, 11, 14}, Right("bb") = {12}, Right("ba") = {4,8,13}

Right(“aaa”) = {6, 10} Right(“aab”) = {3, 7, 11} Right("aba") = {4, 8} Right("baa") = {5, 9} Right("bba") = {13} Right("bab") = {14} Right("abb") = {12}

Right("aaab") = {7, 11} Right(“aaba”) = {4, 8} Right("abaa") = {5, 9} Right("baaa") = {6, 10} Right("aabb") = {12} Right("abba") = {13} Right("bbab") = {14}

再向下由於人類智慧太不好搞了,就不畫了。但是,根據現有的Right集合,或許我們可以發現些什麽。給出壹張圖來直觀地展示:

我們用小學生看圖找特點的思維來壹點點看這張圖。用羅列的方法來找特點。(嘿嘿,其實 是我的思路比較亂)

1、首先要記住壹件事:樹的深度不等於根到這個節點組成的字符串長度。很明顯的,有幾個單個的葉子結點很好的說明了這個特點。

2、到某個節點組成的字符串的長度越長,其Right集合裏面的元素就越少,也就是說,其在串中的可以匹配的位置就越少。

3、壹個節點的Right集合大小等於以其為根的子樹的葉子結點的個數。(這個好像不太明顯,因為 我沒有把整個樹畫完QAQ……不過大家可以自行向下擴展)

4、葉子結點除外,根到壹個結點組成的字符串的長度等於其父親的長度加 + 1,但是我們要清楚的知道,父親的長度是指其Right集合所表示的所有字符串的最長長度。舉個例子來說,對於這樣壹個串,“AABAABAAB“,Rigth("AB") = {3,6,9} Right(”ABB“) = {3,6,9},他們的Right集合是相同的。所以,用這個也可以來解釋 第1 點。樹的深度不等於根到這個節點組成 的字符串的長度。

5、壹個非葉結點至少有兩個兒子。

6、兩個不同的Right集合,其關系要麽是壹個是另壹個的真子集,要麽兩個完全不相交。在樹上這個是很直觀的吧。

我們再來理解壹下pre指針的作用。

某個狀態的pre指針指向的結點是當前結點(cur)Right集合所表示的字符串的最長公***後綴(不是其本身)

好,下面我們來具體說明壹下構建自動機的過程:

在這個過程中我們需要兩個指針,last表示上壹次插入的結點位置,cur表示當前的結點位置。

1、首先是建立壹個空結點,表示空串的狀態,其len = 0, pre = null;這個是很好理解的吧,在Parent樹中,這個結點的角色是樹根。

2、然後假設我們已經構建了前i-1個字符的後綴自動機,現在我們考慮加入第i個字符 x。首先先從last 向 cur連接壹條邊為x的出邊,然後cur.len = last.len + 1,這些都是很顯然的吧。

3、好,現在我們需要確定cur的pre指針的指向。我們現在在Parent樹上沿著last的pre指針向上跳。

如果不小心跳到了NULL,說明當前自動機中沒有x這個字符,那麽很好處理,直接把cur的pre指針指向root,註意是root,而不是NULL。

如果沒有跳到NULL,那麽,如果last->pre沒有x這樣壹條出邊。那麽這情況好說,直接從last->pre向cur連壹條為x的出邊。為什麽要這麽連?我們考慮,我們已知last->pre指向的是當前狀態Right集合所表示的所有字符串的最長公***後綴,我們在當前狀態的字符串後加上了壹個新的字符x,那就相當於在所有的後綴後面都加了壹個x,但是為了保證不重復不遺漏的在後綴上加上這個字符x,所以我們要選擇最長的那個來添加,這樣自然就用到了這個pre指針, 跳到最長後綴的地方。

如果last->pre有這樣壹條出邊。那麽我們就要分兩種情況來討論:

我們用p來代表last->pre,用q來代表last->pre的x出邊。

情況1. 如果q.len == p.len + 1,那麽就把cur的pre設為q。

情況2. 如果q.len > p.len + 1,那麽就要把拷貝壹個新的結點。

情況壹情況二的解釋如下:(來自王夢迪(NOI2015金牌得主)的博客)

第二種情況——當我們進入壹個已存在的轉移(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處結束