2.2　KMP算法

KMP算法是由Knuth、Morris、Pratt共同提出的模式匹配算法。對于任何模式和目標序列，KMP算法都可以在線性時間內完成匹配查找，而不會發生退化，是一個非常優秀的模式匹配算法。但是相較于其他模式匹配算法，該算法晦澀難懂，第一次接觸該算法的讀者往往會感覺一頭霧水，主要原因是KMP算法在構造跳轉表next的過程中進行了多個層面的優化和抽象，使得KMP算法進行模式匹配的原理顯得不是那么直白。本節將深入KMP算法，把該算法的各個細節徹底講透，希望能掃除讀者對該算法的困擾。

2.2.1　KMP算法的原理

KMP算法完成的任務是：給定兩個字符串O和f，其長度分別為n和m，判斷f是否在O中出現，如果出現，則返回到出現的位置。常規方法是遍歷a的每一個位置，然后從該位置開始和b進行匹配，但是這種方法的復雜度是O（nm）。KMP算法通過一個O（m）的預處理，使匹配的復雜度降為O（n+m）。

這里首先用一個圖來描述KMP算法的思想，其原理如圖2.2所示。在字符串O中尋找f，當匹配到位置i時，兩個字符串不相等，這時需要將字符串f向前移動。常規方法是每次向前移動一位，但是它沒有考慮前i-1位已經比較過這個事實，所以效率不高。事實上，如果我們提前計算某些信息，就有可能一次前移多位。假設根據已經獲得的信息知道可以前移k位，分析移位前后的f有什么特點，則可以得到如下的結論：

（1）A段字符串是f的一個前綴。

（2）B段字符串是f的一個后綴。

（3）A段字符串和B段字符串相等。

前移k位之后，可以繼續比較位置i的前提是f的前i-1個位置滿足：長度為i-k-1的前綴A和后綴B相同。只有這樣，才可以在前移k位后從新的位置繼續比較。

KMP算法的核心是計算字符串f的每一個位置之前的字符串的前綴和后綴公共部分的最大長度（不包括字符串本身，否則最大長度始終是字符串本身）。獲得f的每一個位置的最大公共長度之后，就可以利用該最大公共長度快速地和字符串O進行比較。當每次比較到兩個字符串的字符不同時，就可以根據最大公共長度將字符串f向前移動“已匹配長度-最大公共長度”位，接著繼續比較下一個位置。事實上，字符串f的前移只是概念上的前移，只要在比較的時候在最大公共長度之后比較f和O即可達到字符串f前移的目的。

next數組計算：理解了KMP算法的基本原理，下一步就是要獲得字符串f的每一個位置的最大公共長度。這個最大公共長度在算法導論里面被記為next數組。在這里要注意一點，next數組表示的是長度，下標從1開始；但是在遍歷原字符串時，下標還是從0開始的。假設現在已經求得next[1]、next[2]、…、next[i]，分別表示長度為1到i的字符串的前綴和后綴最大公共長度，現在要求next[i+1]。由圖2.2可以看到，如果位置i和位置next[i]處的兩個字符相同（下標從0開始），則next[i+1]等于next[i]加1。如果兩個位置的字符不相同，則可以將長度為next[i]的字符串繼續分割，獲得其最大公共長度next[next[i]]，然后和位置i的字符比較。這是因為長度為next[i]的前綴和后綴都可以分割成相同的子串，如果位置next[next[i]]和位置i的字符相同，則next[i+1]就等于next[next[i]]加1。如果不相等，就可以繼續分割長度為next[next[i]]的字符串，直到字符串的長度為0為止。next數組計算原理如圖2.3所示。

2.2.2　KMP算法的實現

和樸素（Brute Force）算法相比，KMP算法的時間效率就很高了。KMP算法對模板進行預處理的時間復雜度為O（m），字符串匹配的時間復雜度為O（n），這樣的復雜度已經是最優了，因為需要檢查文本串和模板的每個字符，KMP算法的時間復雜度為O（m+n）。

2.2.3　例題講解

例2-2　剪花布條

Time Limit:1000/1000 ms（Java/Others）　Memory Limit:32768/32768 KB（Java/Others）

題目描述：

一條花布條，里面有些圖案，另有一條直接可用的小飾條，里面也有一些圖案。對于給定的花布條和小飾條，計算一下能從花布條中盡可能剪出多少條小飾條。

輸入：

輸入中含有的數據分別是成對出現的花布條和小飾條，二者都是用可見ASCII字符表示的，可見ASCII字符有多少個，花布上就有多少種花紋。花布條和小飾條不會超過1000個字符長，如果遇見“#”字符，則不再進行工作。

輸出：

輸出能從花布條上剪出的最多小飾條的條數，如果一個都沒有，那就輸出0，在每個結果之間應換行。

樣例輸入：

abcde a3

aaaaaa aa

#

樣例輸出：

0

3

題目來源：HDU 2087。

解題思路：

本題可以通過KMP算法解決，題目要求的是給定一個文本串和給定一個模式串，求文本串中有幾個模式串。注意在文本串為“aaaaaa”、模式串為“aa”的時候，ans是3而不是5。

題目實現：