轉(zhuǎn)自 銀河里的星星
涉及到字符串的問(wèn)題，無(wú)外乎這樣一些算法和數(shù)據(jù)結(jié)構(gòu)：自動(dòng)機(jī) KMP算法 Extend-KMP 后綴樹(shù) 后綴數(shù)組 trie樹(shù)trie圖及其應(yīng)用。當(dāng)然這些都是比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)和算法，而這里面最常用和最熟悉的大概是kmp，即使如此還是有相當(dāng)一部分人也不理解kmp，更別說(shuō)其他的了。當(dāng)然一般的字符串問(wèn)題中，我們只要用簡(jiǎn)單的暴力算法就可以解決了，然后如果暴力效率太低，就用個(gè)hash。當(dāng)然hash也是一個(gè)面試中經(jīng)常被用到的方法。這樣看來(lái)，這樣的一些算法和數(shù)據(jù)結(jié)構(gòu)實(shí)際上很少會(huì)被問(wèn)到，不過(guò)如果使用它們一般可以得到很好的線(xiàn)性復(fù)雜度的算法。
老實(shí)說(shuō)，我也一直覺(jué)得字符串問(wèn)題挺復(fù)雜的，出來(lái)一個(gè)如果用暴力，hash搞不定，就很難再想其他的方法，當(dāng)然有些可以用動(dòng)態(tài)規(guī)劃。不過(guò)為了解決這個(gè)老大難問(wèn)題，還是仔細(xì)對(duì)這些算法和數(shù)據(jù)結(jié)構(gòu)研讀了一番。做個(gè)筆記，免得忘了還得重新思考老長(zhǎng)時(shí)間。如果碰到字符串問(wèn)題，也一般不會(huì)超過(guò)這些方法的范圍了。先看一張圖吧，主要說(shuō)明下這些算法數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系。圖中黃色部分主要寫(xiě)明了這些算法和數(shù)據(jù)結(jié)構(gòu)的一些關(guān)鍵點(diǎn)。
圖中可以看到這樣一些關(guān)系：extend-kmp是kmp的擴(kuò)展；ac自動(dòng)機(jī)是kmp的多串形式；它是一個(gè)有限自動(dòng)機(jī)；而trie圖實(shí)際上是一個(gè)確定性有限自動(dòng)機(jī)；ac自動(dòng)機(jī)，trie圖，后綴樹(shù)實(shí)際上都是一種trie；后綴數(shù)組和后綴樹(shù)都是與字符串的后綴集合有關(guān)的數(shù)據(jù)結(jié)構(gòu)；trie圖中的后綴指針和后綴樹(shù)中的后綴鏈接這兩個(gè)概念及其一致。
下面我們來(lái)分別說(shuō)明這些算法和數(shù)據(jù)結(jié)構(gòu)，并對(duì)其涉及的關(guān)鍵問(wèn)題進(jìn)行分析和解釋。
kmp
首先這個(gè)匹配算法，主要思想就是要充分利用上一次的匹配結(jié)果，找到匹配失敗時(shí)，模式串可以向前移動(dòng)的最大距離。這個(gè)最大距離，必須要保證不會(huì)錯(cuò)過(guò)可能的匹配位置，因此這個(gè)最大距離實(shí)際上就是模式串當(dāng)前匹配位置的next數(shù)組值。也就是max{Aj是 Pi 的后綴
整個(gè)過(guò)程是這樣的：
void next_comp(char * str){
}
復(fù)雜度分析：從上面的過(guò)程可以看出，內(nèi)部循環(huán)再不斷的執(zhí)行k =next[k]，而這個(gè)值必然是在縮小，也就是是沒(méi)執(zhí)行一次k至少減少1；另一方面k的初值是0，而最多++N次，而k始終保持非負(fù)，很明顯減少的不可能大于增加的那些，所以整個(gè)過(guò)程的復(fù)雜度是O(N)。
上面是next數(shù)組的計(jì)算過(guò)程，而整個(gè)kmp的匹配過(guò)程與此類(lèi)似。
extend-kmp[示例代碼]
為什么叫做擴(kuò)展-kmp呢，首先我們看它計(jì)算的內(nèi)容，它是要求出字符串B的后綴與字符串A的最長(zhǎng)公共前綴。extend[i]表示B[i...B_len]與A的最長(zhǎng)公共前綴長(zhǎng)度，也就是要計(jì)算這個(gè)數(shù)組。
觀察這個(gè)數(shù)組可以知道，kmp可以判斷A是否是B的一個(gè)子串，并且找到第一個(gè)匹配位置？而對(duì)于extend[]數(shù)組來(lái)說(shuō)，則可以利用它直接解決匹配問(wèn)題，只要看extend[]數(shù)組元素是否有一個(gè)等于len_A即可。顯然這個(gè)數(shù)組保存了更多更豐富的信息，即B的每個(gè)位置與A的匹配長(zhǎng)度。
計(jì)算這個(gè)數(shù)組extend也采用了于kmp類(lèi)似的過(guò)程。首先也是需要計(jì)算字符串A與自身后綴的最長(zhǎng)公共前綴長(zhǎng)度。我們?cè)O(shè)為next[]數(shù)組。當(dāng)然這里next數(shù)組的含義與kmp里的有所過(guò)程。但它的計(jì)算，也是利用了已經(jīng)計(jì)算出來(lái)的next[1...i-1]來(lái)找到next[i]的大小，整體的思路是一樣的。
具體是這樣的：觀察下圖可以發(fā)現(xiàn)
首先在1...i-1,要找到一個(gè)k，使得它滿(mǎn)足k+next[k]-1最大，也就是說(shuō)，讓k加上next[k]長(zhǎng)度盡量長(zhǎng)。
實(shí)際上下面的證明過(guò)程中就是利用了每次計(jì)算后k+next[k]始終只增不減，而它很明顯有個(gè)上界，來(lái)證明整個(gè)計(jì)算過(guò)程復(fù)雜度是線(xiàn)性的。如下圖所示，假設(shè)我們已經(jīng)找到這樣的k，然后看怎么計(jì)算next[i]的值。設(shè)len= k+next[k]-1(圖中我們用Ak代表next[k]),分情況討論：
如果len < i也就是說(shuō)，len的長(zhǎng)度還未覆蓋到Ai,這樣我們只要從頭開(kāi)始比較A[i...n]與A的最長(zhǎng)公共前綴即可，這種情況下很明顯的，每比較一次，必然就會(huì)讓i+next[i]-1增加一.
如果len >=i,就是我們?cè)趫D中表達(dá)的情形，這時(shí)我們可以看到i這個(gè)位置現(xiàn)在等于i-k+1這個(gè)位置的元素，這樣又分兩種情況
如果 L = next[i-k+1] >=len-i+1,也就是說(shuō)L處在第二條虛線(xiàn)的位置，這樣我們可以看到next[i]的大小，至少是len-i+1,然后我們?cè)購(gòu)拇颂庨_(kāi)始比較后面的還能否匹配，顯然如果多比較一次，也會(huì)讓i+A[i]-1多增加1.
如果 L < len-i+1也就是說(shuō)L處在第一條虛線(xiàn)位置，我們知道A與Ak在這個(gè)位置匹配，但Ak與Ai-k+1在這個(gè)位置不匹配，顯然A與與Ai-k+1在這個(gè)位置也不會(huì)匹配，故next[i]的值就是L。
這樣next[i]的值就被計(jì)算出來(lái)了，從上面的過(guò)程中我們可以看到，next[i]要么可以直接由k這個(gè)位置計(jì)算出來(lái)，要么需要在逐個(gè)比較，但是如果需要比較，則每次比較會(huì)讓k+next[k]-1的最大值加1.而整個(gè)過(guò)程中這個(gè)值只增不減，而且它有一個(gè)很明顯的上界k+next[k]-1< 2*len_A,可見(jiàn)比較的次數(shù)要被限制到這個(gè)數(shù)值之內(nèi)，因此總的復(fù)雜度將是O(N)的。
trie樹(shù)
首先trie樹(shù)實(shí)際上就是一些字符串組成的一個(gè)字符查找樹(shù)，邊由代表組成字符串的字符代表，這樣我們就可以在O(len(str))時(shí)間里判斷某個(gè)字符串是否屬于該集合。trie樹(shù)的節(jié)點(diǎn)內(nèi)分支可以用鏈表也可以用數(shù)組實(shí)現(xiàn)，各有優(yōu)劣。
簡(jiǎn)單的trie樹(shù)每條邊由一個(gè)字符代表，但是為了節(jié)省空間，可以讓邊代表一段字符，這就是trie的壓縮表示。通過(guò)壓縮表示可以使得trie的空間復(fù)雜度與單詞節(jié)點(diǎn)數(shù)目成正比。
AC自動(dòng)機(jī)【示例代碼】
ac自動(dòng)機(jī)，可以看成是kmp在多字符串情況下擴(kuò)展形式，可以用來(lái)處理多模式串匹配。只要為這些模式串建立一個(gè)trie樹(shù)，然后再為每個(gè)節(jié)點(diǎn)建立一個(gè)失敗指針，也就是類(lèi)似與kmp的next函數(shù)，讓我們知道如果匹配失敗，可以再?gòu)哪膫€(gè)位置重新開(kāi)始匹配。ac實(shí)際上兩個(gè)人的名字的首字母，Aho-Corasick。
應(yīng)該還記得，在kmp構(gòu)造next數(shù)組時(shí)，我們是從前往后構(gòu)造，即先構(gòu)造1...i-1，然后再利用它們計(jì)算next[i],這里也是類(lèi)似。不過(guò)這個(gè)先后，是通過(guò)bfs的順序來(lái)體現(xiàn)的。AC自動(dòng)機(jī)的失敗指針具有同樣的功能，也就是說(shuō)當(dāng)我們的模式串在Tire上進(jìn)行匹配時(shí)，如果與當(dāng)前節(jié)點(diǎn)的關(guān)鍵字不能繼續(xù)匹配的時(shí)候，就應(yīng)該去當(dāng)前節(jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn)繼續(xù)進(jìn)行匹配。而從根到這個(gè)失敗指針指向的節(jié)點(diǎn)組成的字符串，實(shí)際上就是跟當(dāng)前節(jié)點(diǎn)的后綴的匹配最長(zhǎng)的字符串。
過(guò)程如下：
--------------引用：AC(Aho-Corasick)自動(dòng)機(jī)算法http://hi.baidu.com/luyade1987/blog/item/5ba280828dcb9eb96d811972
如同KMP中模式串得自我匹配一樣.從根節(jié)點(diǎn)開(kāi)始,對(duì)于每個(gè)結(jié)點(diǎn):設(shè)該結(jié)點(diǎn)上得字符為k,沿著其父親結(jié)點(diǎn)得失敗指針走,直到到達(dá)根節(jié)點(diǎn)或者當(dāng)前失敗指針結(jié)點(diǎn)也存在字符為k得兒子結(jié)點(diǎn),
那么前一種情況當(dāng)然是把失敗指針設(shè)為根節(jié)點(diǎn),而后一種情況則設(shè)為當(dāng)前失敗指針結(jié)點(diǎn)得字符為k得兒子結(jié)點(diǎn).
我們也可以動(dòng)手操作一下，如果我們的ac自動(dòng)機(jī)只包含一個(gè)模式串，這個(gè)過(guò)程實(shí)際上就是kmp的計(jì)算過(guò)程。
接下來(lái)要做的就是進(jìn)行文本匹配:
首先，Trie-(模式串集合)中有一個(gè)指針p1指向root,而文本串中有一個(gè)指針p2指向串頭。下面的操作和KMP很類(lèi)似：如果設(shè)k為p2指向的字母,而在Trie中p1指向的節(jié)點(diǎn)存在字符為k的兒子，那么p2++,p1
則改為指向那個(gè)字符為k的兒子,否則p1順著當(dāng)前節(jié)點(diǎn)的失敗指針向上找，直到p1存在一個(gè)字符為k的兒子,或者p1指向根結(jié)點(diǎn)。如果p1路過(guò)一個(gè)標(biāo)記為模式串終點(diǎn)的結(jié)點(diǎn)，那么以這個(gè)點(diǎn)為終點(diǎn)的的模式
串就已經(jīng)匹配過(guò)了.或者如果p1所在的點(diǎn)可以順著失敗指針走到一個(gè)模式串的終結(jié)結(jié)點(diǎn)，那么以那個(gè)結(jié)點(diǎn)結(jié)尾的模式串也已經(jīng)匹配過(guò)了。
在下面的鏈接中可以找到相關(guān)的資料:
www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
主要是根據(jù)模式串構(gòu)造三個(gè)函數(shù)goto fail和output.
q := 0; // initial state (root)
for i := 1 to m do
while g(q, T[i]) = 0 do
q := f(q); // follow a fail
q := g(q, T[i]); // follow a goto
if out(q) != 0; then print i, out(q);
endfor;
-----------------------------------------引用結(jié)束-------------------------------------------------------------------------------------------
以ababa為例，我們可以得到它的kmp next數(shù)組值為 0 0 1 2 3,ac自動(dòng)機(jī)和trie圖如下：
trie圖【示例代碼】
trie圖實(shí)際上一個(gè)確定性自動(dòng)機(jī)，比ac增加了確定性這個(gè)屬性，對(duì)于ac自動(dòng)機(jī)來(lái)說(shuō)，當(dāng)碰到一個(gè)不匹配的節(jié)點(diǎn)后可能要進(jìn)行好幾次回溯才能進(jìn)行下一次匹配。但是對(duì)于trie圖來(lái)說(shuō)，可以每一步進(jìn)行一次匹配，每碰到一個(gè)輸入字符都有一個(gè)確定的狀態(tài)節(jié)點(diǎn)。
從上面的圖中我們也可以看到trie圖的后綴節(jié)點(diǎn)跟ac自動(dòng)機(jī)的后綴指針基本一致，區(qū)別在于trie圖的根添加了了所有字符集的邊。另外trie圖還會(huì)為每個(gè)節(jié)點(diǎn)補(bǔ)上所有字符集中的字符的邊，而這個(gè)補(bǔ)邊的過(guò)程實(shí)際上也是一個(gè)求節(jié)點(diǎn)的后綴節(jié)點(diǎn)的過(guò)程，不過(guò)這些節(jié)點(diǎn)都是虛的，我們不把它們加到圖中，而是找到它們的等價(jià)節(jié)點(diǎn)即它們的后綴節(jié)點(diǎn)，從而讓這些邊指向后綴節(jié)點(diǎn)就可以了。(比如上圖中的黑節(jié)點(diǎn)c，它實(shí)際上并未出現(xiàn)在我們的初始tire里，但我們可以把它作為一個(gè)虛節(jié)點(diǎn)處理，把指向它的邊指向它的后綴節(jié)點(diǎn))
trie圖主要利用兩個(gè)概念實(shí)現(xiàn)這種目的。一個(gè)是后綴節(jié)點(diǎn)，也就是每個(gè)節(jié)點(diǎn)的路徑字符串去掉第一個(gè)字符后的字符串對(duì)應(yīng)的節(jié)點(diǎn)。計(jì)算這個(gè)節(jié)點(diǎn)的方法，是通過(guò)它父親節(jié)點(diǎn)的后綴節(jié)點(diǎn)，很明顯它父親的后綴節(jié)點(diǎn)與它的后綴節(jié)點(diǎn)的區(qū)別就是還少一個(gè)尾字符，設(shè)為c。所以節(jié)點(diǎn)的父節(jié)點(diǎn)的指針的c孩子就是該節(jié)點(diǎn)的后綴節(jié)點(diǎn)。但是因?yàn)橛袝r(shí)候它父親不一定有c孩子，所以還得找一個(gè)與父親的c孩子等價(jià)的節(jié)點(diǎn)。于是就碰到一個(gè)尋找等價(jià)節(jié)點(diǎn)的問(wèn)題。
而trie圖還有一個(gè)補(bǔ)邊的操作，不存在的那個(gè)字符對(duì)應(yīng)的邊指向的節(jié)點(diǎn)實(shí)際上可以看成一個(gè)虛節(jié)點(diǎn)，我們要找一個(gè)現(xiàn)有的并且與它等價(jià)的節(jié)點(diǎn)，將這個(gè)邊指向它。這樣也實(shí)際上是要尋找等價(jià)節(jié)點(diǎn)。
我們看怎么找到一個(gè)節(jié)點(diǎn)的等價(jià)節(jié)點(diǎn)，我們所謂的等價(jià)是指它們的危險(xiǎn)性一致。那我們?cè)倏匆粋€(gè)節(jié)點(diǎn)是危險(xiǎn)節(jié)點(diǎn)的充要條件是：它的路徑字符串本身就是一個(gè)危險(xiǎn)單詞，或者它的路徑字符串的后綴對(duì)應(yīng)的節(jié)點(diǎn)是一個(gè)危險(xiǎn)節(jié)點(diǎn)。因此我們可以看到，如果這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的路徑字符串本身不是一個(gè)危險(xiǎn)單詞，那它就與它的后綴節(jié)點(diǎn)是等價(jià)的。所以我們補(bǔ)邊的時(shí)候，實(shí)際指向的是節(jié)點(diǎn)的后綴節(jié)點(diǎn)就可以了。
trie圖實(shí)際上對(duì)trie樹(shù)進(jìn)行了改進(jìn)，添加了額外的信息。使得可以利用它方便的解決多模式串的匹配問(wèn)題。跟kmp的思想一樣，trie圖也是希望利用現(xiàn)在已經(jīng)匹配的信息，對(duì)未來(lái)的匹配提出指導(dǎo)。提出了一些新的概念。定義trie樹(shù)上，從根到某個(gè)節(jié)點(diǎn)的路徑上所有邊上的字符連起來(lái)形成的字符串稱(chēng)為這個(gè)節(jié)點(diǎn)的路徑字符串。如果某個(gè)節(jié)點(diǎn)的路徑字符串以一個(gè)危險(xiǎn)字符串結(jié)尾，那么這個(gè)節(jié)點(diǎn)就是危險(xiǎn)節(jié)點(diǎn)：也就是說(shuō)如果到達(dá)這個(gè)點(diǎn)代表是匹配的狀態(tài)；否則就是安全節(jié)點(diǎn)。那么如何判斷某個(gè)節(jié)點(diǎn)是否危險(xiǎn)呢？
根節(jié)點(diǎn)顯然是安全節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)是危險(xiǎn)節(jié)點(diǎn)的充要條件是：它的路徑字符串本身就是一個(gè)危險(xiǎn)單詞，或者它的路徑字符串的后綴(這里特指一個(gè)字符串去掉第一個(gè)字符后剩余的部分)對(duì)應(yīng)的節(jié)點(diǎn)(一個(gè)字符串對(duì)應(yīng)的節(jié)點(diǎn)，是指從trie圖中的根節(jié)點(diǎn)開(kāi)始，依次沿某個(gè)字符指定的邊到達(dá)的節(jié)點(diǎn))是一個(gè)危險(xiǎn)節(jié)點(diǎn)。
那么如何求每一個(gè)節(jié)點(diǎn)的后綴節(jié)點(diǎn)呢？這里就可以里利用以前的計(jì)算信息，得到了。具體來(lái)說(shuō)就是利用父親節(jié)點(diǎn)的后綴節(jié)點(diǎn)，我們只要記住當(dāng)前節(jié)點(diǎn)的最后一個(gè)字符設(shè)為C，那么父親節(jié)點(diǎn)的后綴節(jié)點(diǎn)的C分支節(jié)點(diǎn)就是要求的后綴節(jié)點(diǎn)了。首先我們限定，根節(jié)點(diǎn)的后綴節(jié)點(diǎn)是根本身，第一層節(jié)點(diǎn)的后綴節(jié)點(diǎn)是根節(jié)點(diǎn)。這樣我們可以逐層求出所有節(jié)點(diǎn)的后綴節(jié)點(diǎn)。但是這個(gè)過(guò)程中，可能出現(xiàn)一個(gè)問(wèn)題：父親節(jié)點(diǎn)的后綴節(jié)點(diǎn)可能沒(méi)有c分支。這時(shí)候該怎么辦呢？
如下圖所示如果設(shè)當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)的后綴節(jié)點(diǎn)為w，我們假設(shè)w具有c孩子為，我們可以看到對(duì)于w的整個(gè)c子樹(shù)來(lái)說(shuō)，因?yàn)楦静淮嬖谕ㄏ蛩鼈兊倪卌，它們也就不可能是不良字符串，這樣這些節(jié)點(diǎn)的危險(xiǎn)性也就等價(jià)與它們的后綴節(jié)點(diǎn)的危險(xiǎn)性了，而它們的后綴節(jié)點(diǎn)，實(shí)際上就是w的后綴節(jié)點(diǎn)的c孩子，如此回溯下去，最后就能找到。
--------------------引用：http://huangwei.host7.meyu.net/?paged=7
其實(shí)Trie圖所起到的作用就是建立一個(gè)確定性有限自動(dòng)機(jī)DFA，圖中的每點(diǎn)都是一個(gè)狀態(tài)，狀態(tài)之間的轉(zhuǎn)換用有向邊來(lái)表示。Trie圖是在Tire的基礎(chǔ)上補(bǔ)邊過(guò)來(lái)的，其實(shí)他應(yīng)該算是AC自動(dòng)機(jī)的衍生，AC自動(dòng)機(jī)只保存其后綴節(jié)點(diǎn)，在使用時(shí)再利用后綴節(jié)點(diǎn)進(jìn)行跳轉(zhuǎn)，并一直迭代到找到相應(yīng)的狀態(tài)轉(zhuǎn)移為止，這個(gè)應(yīng)該算是KMP的思想。這篇文章可以參考。
而Trie圖直接將AC自動(dòng)機(jī)在狀態(tài)轉(zhuǎn)移計(jì)算后的值保存在當(dāng)前節(jié)點(diǎn)，使得不必再對(duì)后綴節(jié)點(diǎn)進(jìn)行迭代。所以Trie圖的每個(gè)節(jié)點(diǎn)都會(huì)有|∑|個(gè)狀態(tài)轉(zhuǎn)移（∑指字符集）。構(gòu)造具體方法可見(jiàn)WC2006《Trie圖的構(gòu)建、活用與改進(jìn)》。我簡(jiǎn)單敘述下流程：
（1）構(gòu)建Trie，并保證根節(jié)點(diǎn)一定有|∑|個(gè)兒子。
（2）層次遍歷Trie，計(jì)算后綴節(jié)點(diǎn)，節(jié)點(diǎn)標(biāo)記，沒(méi)有|∑|個(gè)兒子的對(duì)其進(jìn)行補(bǔ)邊。
后綴節(jié)點(diǎn)的計(jì)算：
（1）根結(jié)點(diǎn)的后綴節(jié)點(diǎn)是它本身。
（2）處于Trie樹(shù)第二層的節(jié)點(diǎn)的后綴結(jié)點(diǎn)也是根結(jié)點(diǎn)。
（3）其余節(jié)點(diǎn)的后綴節(jié)點(diǎn)，是其父節(jié)點(diǎn)的后綴節(jié)點(diǎn)中有相應(yīng)狀態(tài)轉(zhuǎn)移的節(jié)點(diǎn)（這里類(lèi)似AC自動(dòng)機(jī)的迭代過(guò)程）。
節(jié)點(diǎn)標(biāo)記：
（1）本身就有標(biāo)記。
（2）其后綴節(jié)點(diǎn)有標(biāo)記。
補(bǔ)邊：
用其后綴節(jié)點(diǎn)相應(yīng)的狀態(tài)轉(zhuǎn)移來(lái)填補(bǔ)當(dāng)前節(jié)點(diǎn)的空白。
最后Trie圖中任意一個(gè)節(jié)點(diǎn)均有相應(yīng)的狀態(tài)轉(zhuǎn)移，我們就用這個(gè)狀態(tài)轉(zhuǎn)移做動(dòng)態(tài)規(guī)劃。
設(shè)dp[i][j]表示第i個(gè)狀態(tài)產(chǎn)生j個(gè)字符時(shí)，與DNA序列最小的改變值。
假設(shè)Tire圖中根節(jié)點(diǎn)是0，則初始化dp[0][0]=1。
其后，對(duì)圖進(jìn)行BFS遍歷，可知處于第j層時(shí)，就說(shuō)明以產(chǎn)生了j長(zhǎng)度的字符串。
dp[0][0] = 1;for i = 1 to m do
-----------------------------------------------引用結(jié)束-----------------------------------------------------------------------------------
后綴樹(shù)
后綴樹(shù)，實(shí)際上就是字符串的所有后綴組成的字符串集合構(gòu)成的trie樹(shù)。如果采用不壓縮方式的trie存儲(chǔ)，這樣整個(gè)內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)的總和就可能達(dá)到O(n^2).所以不能利用這種存儲(chǔ)方式，因?yàn)槿绻捎盟敲礃?gòu)建的復(fù)雜度下界就是O(n^2)，不會(huì)再低了。所以必須使用壓縮方式，才有可能降到O(n)。
構(gòu)建之前，我們首先給字符串加上一個(gè)未在字符串中出現(xiàn)過(guò)的單詞，比如"$",為什么這樣做呢？是為了避免后綴節(jié)點(diǎn)出現(xiàn)在內(nèi)部，如果我們加上"$"，很明顯就不會(huì)有后綴出現(xiàn)在內(nèi)部了，可以用反證法證明：假設(shè)出現(xiàn)了一個(gè)這樣的后綴是內(nèi)部節(jié)點(diǎn)，那么意味著這條字符串路徑上會(huì)有兩個(gè)"$",但這是不可能的，因?yàn)槲覀兊?$"只在結(jié)尾出現(xiàn)，之前沒(méi)有出現(xiàn)過(guò)。
構(gòu)建過(guò)程中，我們看如果采用普通的構(gòu)建過(guò)程是怎樣的？普通的構(gòu)建，假設(shè)字符串為A[1....N],我們從以A[1]開(kāi)頭的后綴開(kāi)始插入trie樹(shù)，插入的時(shí)候，逐步比對(duì)，直到找到不匹配的分支，在這個(gè)節(jié)點(diǎn)將原來(lái)的節(jié)點(diǎn)分裂，并加入這個(gè)新的節(jié)點(diǎn)?？梢赃@個(gè)過(guò)程關(guān)鍵是尋找，之前sufix[1]...sufix[i-1]這些已經(jīng)插入的字符串與sufix[i]的最長(zhǎng)公共前綴。之后插入的時(shí)間O(1)就可以完成，因此主要的時(shí)間花在這個(gè)最長(zhǎng)公共前綴(稱(chēng)為head[i])的尋找上。Headi是W(i,n)和W(j,n)的最長(zhǎng)公共前綴，其中j是小于i的任意正整數(shù)，Taili使得Headi+ Taili = W(i,n)。
那我們看到現(xiàn)在關(guān)鍵是這個(gè)最長(zhǎng)公共前綴head[i]的計(jì)算了。我們?cè)俅慰紤]如何利用head[1]...head[i-1]來(lái)計(jì)算head[i],為加快尋找hi的速度我們需要使用輔助結(jié)構(gòu)——后綴鏈接。
后綴鏈接的定義（McCreight Arithmetic）：
令Head[i-1] =az，其中a是字符串W的第i-1位字符。由于z在范圍i內(nèi)出現(xiàn)過(guò)至少兩次(因?yàn)閍z也是A[i-1...N]與之前某后綴的最長(zhǎng)公共前綴，也就是說(shuō)另外的那個(gè)后綴也是一az開(kāi)頭的一個(gè)串，這樣就意味著它的后繼者，就比然是以z為前綴的，這樣A[i...N]與它的公共前綴就是z。{實(shí)際上這個(gè)性質(zhì)在我們計(jì)算后綴數(shù)組的lcp時(shí)也會(huì)利用到})，所以一定有|Head[i]|>=
和前面 ac自動(dòng)機(jī)的失敗指針trie樹(shù)的后綴指針比較，我們可以發(fā)現(xiàn)這里的z它剛好就是head[i-1]去掉第一個(gè)字符后的那個(gè)后綴，所謂的后綴鏈接，實(shí)際上是指向head[i]自身的后綴的鏈接，這個(gè)定義也就跟我們trie樹(shù)里的后綴指針?biāo)赶虻哪莻€(gè)位置一致了。這樣這個(gè)head[i]的后綴鏈接怎樣建立就很清楚了。
創(chuàng)建方法：
1）根節(jié)點(diǎn)Root的后綴鏈接指向它自身
2）任何一個(gè)非葉節(jié)點(diǎn)的后綴鏈接都在該節(jié)點(diǎn)出現(xiàn)以后被立即創(chuàng)建
算法主框架如下：
For i = 1 -> n do
End for
后綴樹(shù)性能分析：
接著剛才文本框內(nèi)的偽代碼來(lái)談?wù)摗?duì)于給定的i，步驟2的復(fù)雜度為O(1)，但由于無(wú)法確定Linkhi-1到hi之間的節(jié)點(diǎn)個(gè)數(shù)，所以不能保證步驟1總是線(xiàn)性的。局部估算失敗，不妨從整體入手。有一點(diǎn)是肯定的，那就是i +|Headi|總隨著i的遞增而遞增。因此，W中的每個(gè)字符只會(huì)被Find函數(shù)遍歷1次，總體復(fù)雜度是O(n)的。
這個(gè)分析就與extend-kmp的復(fù)雜度分析很類(lèi)似了。
后綴數(shù)組[示例代碼]
后綴數(shù)組實(shí)際上就是對(duì)字符串的后綴按照字典序進(jìn)行排序，然后把排好序后的順序放到一個(gè)數(shù)組sa[]里保存，數(shù)組元素代表了后綴在原串里的起始索引。通過(guò)這個(gè)我們可以很容易得到另一個(gè)數(shù)組rank[],rank[i]代表了原來(lái)的后綴A[i...N]在sa數(shù)組里的排名。
這個(gè)數(shù)據(jù)結(jié)構(gòu)，主要涉及兩個(gè)方面的內(nèi)容，一個(gè)是如何快速的對(duì)這些后綴排序，有很多方法，這里只說(shuō)明倍增算法，這個(gè)方法比較好理解，思路也比較巧妙。
還有就是后綴數(shù)組求出來(lái)后，如果要發(fā)揮比較強(qiáng)的作用，還需要求出各個(gè)后綴的最長(zhǎng)公共前綴lcs。所以lcs的計(jì)算也是一個(gè)重點(diǎn)。
首先看排序，如果我們采用普通的排序算法，那么需要nlogn次比較，但是每次比較需要O(n),這樣總的復(fù)雜度將是O(n*nlogn).
倍增算法是這樣的,主要是第i次排序，比較時(shí)的大小時(shí)利用了第i-1次的排序結(jié)果，這樣可以讓比較在O(1)時(shí)間里完成：
我們首先對(duì)所有從原字符串各個(gè)位置開(kāi)始的長(zhǎng)度為1的字符進(jìn)行排序，然后再對(duì)從這些位置開(kāi)始的長(zhǎng)度為2的排序，之后是長(zhǎng)度為2^i的排序，直到2^i>= N.可以看到這中間，總共需要logN次排序。然后我們看第i次排序，比較大小時(shí)怎樣利用了第i-1次的排序結(jié)果。
比如在第i次排序時(shí)，我們需要比較A[j]和A[k]開(kāi)始的長(zhǎng)度為2^i的串，那么我們可以將它們分成兩塊：
A[j]開(kāi)始的長(zhǎng)度為2^i的串 = A[j]開(kāi)始的2^(i-1)長(zhǎng) + A[j+2^(i-1)]開(kāi)始的2^(i-1)長(zhǎng)
A[k]開(kāi)始的長(zhǎng)度為2^i的串 = A[k]開(kāi)始的2^(i-1)長(zhǎng) + A[k+2^(i-1)]開(kāi)始的2^(i-1)長(zhǎng)
要比較A[j]開(kāi)始的長(zhǎng)度為2^i的串 和A[k]開(kāi)始的長(zhǎng)度為2^i的串，我們只要先比較第一部分，如相等再比較第2部分，而這兩部分大小因?yàn)橹耙呀?jīng)排好序了，我們完全可以給它們一個(gè)rank值，只比較它們的rank值就可以得到大小關(guān)系，這樣比較就可以在O(1)時(shí)間內(nèi)完成了。另外如果我們的排序算法是O(n)的，這樣整個(gè)算法的復(fù)雜度就是O(nlogn)的了。
再看lcs的計(jì)算，如果要計(jì)算任意兩個(gè)后綴的lcs[i][j]，我們有一個(gè)結(jié)論：
設(shè) i<j
如果要證明上面那個(gè)結(jié)論，首先要證明這個(gè)：對(duì)任意的1=<i<j<k<=n,LCP(i,k)=min{LCP(i,j),LCP(j,k)}，這里不再證明。
上面那個(gè)結(jié)論實(shí)際上說(shuō)：如果要找i j的最長(zhǎng)公共前綴長(zhǎng)度，只需要找到ij之間相鄰后綴的最小lcs長(zhǎng)度即可。這樣我們只需要求出sa數(shù)組中相鄰后綴的lcs長(zhǎng)度，就轉(zhuǎn)化成了一個(gè)rmq問(wèn)題，即區(qū)間內(nèi)的最小值問(wèn)題。這個(gè)可以O(shè)(1)解決。這樣問(wèn)題就變成：如何在O(n)時(shí)間里，計(jì)算sa數(shù)組中相鄰后綴的lcs長(zhǎng)度。
這個(gè)問(wèn)題如果要O(n)，又利用了下面這樣一個(gè)結(jié)論：定義一個(gè)一維數(shù)組 height，令height[i]=LCP(i-1,i)1<i<=n 并設(shè)height[1]=0。如何盡量高效的算出height數(shù)組呢？
為了描述方便，設(shè)h[i]=height[Rank[i]]，即height[i]=h[SA[i]]，而h數(shù)組滿(mǎn)足一個(gè)性質(zhì)：
對(duì)于 i>1 且Rank[i]>1
為什么會(huì)有這個(gè)結(jié)論呢？實(shí)際上就與上面后綴樹(shù)的后綴鏈接那部分提到的想呼應(yīng)了。h[i]=height[Rank[i]],實(shí)際上就是我們的原來(lái)的后綴A[i...N]與某個(gè)串的最長(zhǎng)公共前綴，而h[i-1]就是A[i-1...N]與某個(gè)串的最長(zhǎng)公共前綴。而我們可以看到如果把A[i-1...N]去掉第一個(gè)字符后，就變成了A[i...N]，我們假設(shè)A[i-1...N]相鄰的那個(gè)后綴串是XYYYYYY，在這里它們的lcs長(zhǎng)度是h[i]。后綴串XYYYYYY，去掉x之后就是YYYYYYY,這樣如果沒(méi)有比它更接近A[i...N]的,那么h[i]=h[i-1]-1,如果A[i...N]的鄰居不是它，那么h[i]只可能比h[i-1]-1大不可能比它小。
這樣利用這個(gè)結(jié)論，我們?cè)贠(n)時(shí)間內(nèi)就可以把h[i]計(jì)算出來(lái)了。因?yàn)閔[i]最大不超過(guò)N，而它每次最多減少不超過(guò)1.
計(jì)算出來(lái)之后，再根據(jù)height[i]=h[SA[i]]，就可以計(jì)算出height數(shù)組，這樣就求出了sa中相鄰后綴的lcs長(zhǎng)度。
總結(jié)：
實(shí)際上我們可以看到上面的算法思想，都有一個(gè)共同點(diǎn)：利用已經(jīng)得到的計(jì)算結(jié)果得到下一次計(jì)算的結(jié)果，盡量利用現(xiàn)有信息，減少計(jì)算量。
聯(lián)系客服
