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