1 術語定義

在字符串匹配問題中，我們期待察看串T中是否含有串P。
其中串T被稱為目標串，串S被稱為模式串。

2 樸素匹配算法

進行字符串匹配，最簡單的一個想法是：

public ? class ?SimpleMatch? {
?? public ? int ?StringMatch(String?target,String?patten)? {
?????? int ?tl? = ?target.length();
?????? int ?pl? = ?patten.length();
?????? int ?i? = ? 0 ;
?????? int ?j? = ? 0 ;
?????? while (i? < ?tl? - ?pl? && ?j? < ?pl)? {
?????????? if (patten.charAt(j)? == ?target.charAt(i + j))
??????????????j ++ ;
?????????? else ? {
??????????????j? = ? 0 ;
??????????????i ++ ;
??????????}
??????}
?????? if (j? == ?pl)
?????????? return ?i;
?????? return ? - 1 ;
??}
??
?? public ? static ? void ?main(String[]?args) {
??????String?t? = ? " 123456789 " ;
??????String?p? = ? " 456 " ;
??????SimpleMatch?sm? = ? new ?SimpleMatch();
??????System.out.println(sm.StringMatch(t,?p));
??}
}

可以看見，這個算法（假定m>>n）的復雜度是O(mn)，其中m是T的長度，n是P的長度。這種算法的缺陷是匹配過程中帶有回溯——準確地說是T串存在回溯，也就是當匹配不成功的時候，之前進行的匹配完全變為無用功，所有的比較需要重新開始。

3 KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt提出的無回溯的字符串匹配算法，算法的核心思想就是設法在匹配失敗的時候，盡量利用之前的匹配結果，消除T串的回溯問題。那么如何消除回溯呢？請看下面的例子：

假設P=abacd，如果T=abax...，當從頭開始匹配到字符c時，若c=x，顯然，匹配過程繼續；當c≠x時，按照樸素的匹配算法，T串會發生回溯，之后T串會從第2個字符b開始重新匹配，而不是從匹配失敗的字符x開始繼續。但是顯然，對于上述的匹配過程，T串不需要從b開始重新匹配，它只需要從x開始和P的b字符繼續匹配即可。如下：
匹配過程：
P=abacd
T=abax....
???? ^----比較到此處時發生匹配失敗
樸素匹配算法：
P= abacd
T=abax...
?? ^----回溯到b，重新開始和P的匹配
KMP算法：
P=? abacd
T=abax...
???? ^----T串不回溯，從x處繼續匹配

現在的問題是，按照KMP算法，匹配失敗的時候，P串需要重新調整位置，但是調整的依據是什么？Knuth等人發現，P調整位置的依據和P的構造有關，和T無關。具體來說，定義失效函數：f(j)=k，其中0<=k<=j，且k是使得p₀p₁...p_k-1 = p_j-k+1p_j-k+2...p_j成立的最大整數。建立失效函數的算法如下：
public void Build() {
?if(pattern == null)
??throw new Exception("KMP Exception : null pattern");
?array = new int[pattern.Length];
?int i = 0, s = pattern.Length;
?if(s > 1)
??array[0] = 0;
?for(i = 1; i < s; i++) {
??if(pattern[i] == pattern[array[i - 1]])
???array[i] = array[i - 1] + 1;
??else
???array[i] = 0;
?}
}

匹配過程如下：
public int Match(String target, int start) {
?if(array == null || pattern == null || target == null)
??return -1;
?int target_index = start;
?int pattern_index = 0;
?int token_length = target.Length;
?int pattern_length = pattern.Length;
?while(target_index < token_length && pattern_index < pattern_length) {
??if(target[target_index] == pattern[pattern_index]) {
???target_index++;
???pattern_index++;
??} else {
???if(pattern_index == begin)
????target_index++;
???else
????pattern_index = array[pattern_index - 1];
??}
?}
?if(pattern_index == pattern_length)
??return target_index - pattern_length;
?return -1;
}

4 支持通配符?和*的KMP算法

KMP算法雖然能夠進行字符串匹配，但是，在實踐中字符串匹配往往還要支持通配符，MS系統中最常見的通配符是?和*。其中，?可以代表一個字符（不能沒有），*可以代表任意多個字符（可以為空）。經典的KMP算法針對通配符是無能為力的，但是經過簡單的改造，KMP算法也可以識別通配符。

首先是?，根據?的功能，?表示任意字符，也就是說在匹配過程中，?永遠匹配成功。因此對匹配函數的修改十分簡單：
...
?while(target_index < token_length && pattern_index < pattern_length) {
??if(target[target_index] == pattern[pattern_index]|| pattern[pattern_index] == '?') {
???target_index++;
???pattern_index++;
??} else {
...
建立失效函數的過程和匹配過程類似，修改如下：
...
?for(i = 1; i < s; i++) {
??if(pattern[i] == pattern[array[i - 1]]|| pattern[i] == '?' || pattern[array[i - 1]] == '?')
???array[i] = array[i - 1] + 1;
...

本質上，?并沒有修改算法，而僅僅修改了匹配規則——遇到?則一定匹配。然而*與此不同，*的作用是匹配任意多個字符，顯然我們不能簡單的修改匹配過程而滿足要求。如果我們重新思考*的作用，我們會發現*的另一個作用就是分割P串，即如果P=P₁*P₂，那么與其說*代表匹配任意多個字符，不如說P的匹配條件是在匹配P₁子串后再匹配P₂子串。

現在回顧失效函數的作用，如果當匹配到P的j+1位時匹配失敗，那么重新開始匹配的時候，P串的位置調整到f(j)位，直到P串的位置調整到0，則匹配重新開始。但當P=P₁*P₂，假如P₁已經匹配成功，而在P₂中發生匹配失敗，那么P串要需要調整位置，但P串無論如何調整，此時也不應該調整到0，最多調整到P₂的開始處，因為P₁已經匹配，只需匹配P₂即可。假如P=abcab*abcab，失效函數應該是（注意之前提到*的作用）：
a b c a b * a b c a b
0 0 0 1 2 - 6 6 6 7 8

因此，要想讓KMP支持*，那么關鍵是要重新設計失效函數的建立算法，如下：
public void Build() {
?if(pattern == null)
??throw new Exception("KMP Exception : null pattern");
?array = new int[pattern.Length];
?int i = 0, s = pattern.Length;
?if(s > 1)
??array[0] = 0;
?int begin = 0;
?for(i = 1; i < s; i++) {
??if(pattern[i] == '*') {
???array[i] = i;
???begin = i + 1;
??} else if(pattern[i] == pattern[array[i - 1]] || pattern[i] == '?' || pattern[array[i - 1]] == '?')
???array[i] = array[i - 1] + 1;
??else
???array[i] = begin;
?}
}?

算法中begin表示每段字符串的開始位置。此外，匹配過程也應該進行相應的修改，因為字符*對于匹配沒有任何幫助，它屬于占位符，因此需要跳過，匹配算法如下：
public int Match(String target, int start) {
?if(array == null || pattern == null || target == null)
??return -1;
?int target_index = start;
?int pattern_index = 0;
?int token_length = target.Length;
?int pattern_length = pattern.Length;
?int begin = 0;
?while(target_index < token_length && pattern_index < pattern_length) {
??if(pattern[pattern_index] == '*') {
???begin = pattern_index + 1;
???pattern_index++;
??} else if(target[target_index] == pattern[pattern_index] || pattern[pattern_index] == '?') {
???target_index++;
???pattern_index++;
??} else {
???if(pattern_index == begin)
????target_index++;
???else
????pattern_index = array[pattern_index - 1];
??}
?}
?if(pattern_index == pattern_length)
??return target_index - pattern_length + begin;
?return -1;
}

5 正則語言和確定狀態自動機

一個數字邏輯的問題：設計一個識別11011的電路，解這個問題的關鍵就是設計出這個電路的DFA，如下：

仔細看看這個狀態機，是不是和KMP的算法有幾分類似呢？這并不是巧合，因為KMP算法中的失效函數總可以等價的轉化為一個DFA。當然KMP的DFA遠比識別11011的DFA要復雜，原因在于KMP接受的輸入是全體字符集合，識別11011的DFA只接受0和1這兩個輸入。我們知道，一個正則語言和一個DFA是等價的，而KMP計算失效函數的算法，實際上等價于求DFA的過程，f(j)的值實際上表明狀態j+1接受到不正確的字符時應該回溯到的狀態（注意此時輸入流并沒有前進）。普通的字符串都能看成是一個正則語言，含有通配符?和*的字符串也可以等價的轉換為一個正則表達式。但是，正則語言的集合遠比KMP算法所能支持的模式集合的更大，期間原因還是剛才提過的輸入問題。試想P=p₁p₂...p_n，當匹配到p_j的時候，如果下一個輸入字符正是p_j，那么狀態機進入下一個狀態，如果不是p_j，那么狀態機按照實效函數的指示轉移到狀態f(j-1)，也就是說KMP狀態機的每個狀態只能根據輸入是否為p_j來進行轉移。而正則表達式所對應的狀態機則有所不同，如果正則語言L=l₁l₂...l_n，假設這些都是字母，當匹配到l_j位的時候，如果下一個輸入字符正是l_j，那么狀態機進入下一個狀態，否則它還可以根據輸入的值進行轉移，例如l_j=c₁時轉換到狀態x，l_j=c₂時狀態轉換到y等等。

6 結語

字符串匹配問題是老問題了，并沒有太多新意可言，只不過雖然KMP算法十分簡單，但它的內在含義還是十分深刻的。橫向比較KMP、DFA和正則語言、正則表達式我們會發現，它們之間存在很多的關聯，而這種比較也有利于我們更好的理解這些算法，或者改進這些算法。最后說一句，試圖利用目前的框架使得KMP算法支持全部種類的通配符（對應于正則表達式就是x?、x*、x+、{m,n}等等）是不可能，而我們也不需要這么做，因為我們還有正則表達式嘛。