1 術(shù)語定義

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

2 樸素匹配算法

進(jìn)行字符串匹配，最簡單的一個(gè)想法是：

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));
??}
}

可以看見，這個(gè)算法（假定m>>n）的復(fù)雜度是O(mn)，其中m是T的長度，n是P的長度。這種算法的缺陷是匹配過程中帶有回溯——準(zhǔn)確地說是T串存在回溯，也就是當(dāng)匹配不成功的時(shí)候，之前進(jìn)行的匹配完全變?yōu)闊o用功，所有的比較需要重新開始。

3 KMP算法

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

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

現(xiàn)在的問題是，按照KMP算法，匹配失敗的時(shí)候，P串需要重新調(diào)整位置，但是調(diào)整的依據(jù)是什么？Knuth等人發(fā)現(xiàn)，P調(diào)整位置的依據(jù)和P的構(gòu)造有關(guān)，和T無關(guān)。具體來說，定義失效函數(shù)：f(j)=k，其中0<=k<=j，且k是使得p₀p₁...p_k-1 = p_j-k+1p_j-k+2...p_j成立的最大整數(shù)。建立失效函數(shù)的算法如下：
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算法雖然能夠進(jìn)行字符串匹配，但是，在實(shí)踐中字符串匹配往往還要支持通配符，MS系統(tǒng)中最常見的通配符是?和*。其中，?可以代表一個(gè)字符（不能沒有），*可以代表任意多個(gè)字符（可以為空）。經(jīng)典的KMP算法針對(duì)通配符是無能為力的，但是經(jīng)過簡單的改造，KMP算法也可以識(shí)別通配符。

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

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

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

因此，要想讓KMP支持*，那么關(guān)鍵是要重新設(shè)計(jì)失效函數(shù)的建立算法，如下：
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表示每段字符串的開始位置。此外，匹配過程也應(yīng)該進(jìn)行相應(yīng)的修改，因?yàn)樽址?對(duì)于匹配沒有任何幫助，它屬于占位符，因此需要跳過，匹配算法如下：
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 正則語言和確定狀態(tài)自動(dòng)機(jī)

一個(gè)數(shù)字邏輯的問題：設(shè)計(jì)一個(gè)識(shí)別11011的電路，解這個(gè)問題的關(guān)鍵就是設(shè)計(jì)出這個(gè)電路的DFA，如下：

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

6 結(jié)語

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