整理了一下?lián)f由于過于晦澀難懂而導致某系統(tǒng)程序猿直接在實現(xiàn)字符串匹配的時候直接用暴力算法代替的KMP算法沼侣，初看之時確實覺得難以理解恨憎，不過經過塞得威客大大一節(jié)課的講解之后谍失，我好像開始明白了拌滋。
其實在真實的應用中當字母表很大重復字符不多模式串很短（模式串一直都很短吧）的時候哥谷，KMP算法并不一定比暴力算法快棺榔，但是KMP算法不回退文本指針的特性使得它可以用來處理字符流中的匹配問題瓶堕。而且如果像0101010111000這樣的字母表就是0，1的字符串的話KMP的算法的效率優(yōu)勢就會體現(xiàn)出來症歇。
這門課中的KMP算法是用有限狀態(tài)自動機（DFA）來實現(xiàn)的郎笆，代碼很短，但是非常的贊（高德納大神的智慧熠熠生輝）忘晤，首先來看一下暴力字符串匹配法：
public class BruteForce {
public static void main(String[] args){
String txt = "ABACCABCFT";
String pat = "FT";
int a = search(pat, txt);
if (a == txt.length()){
System.out.println("Not Found!");
}else{
System.out.println("Found: " + a);
}
}
private static int search(String pat, String txt){
int M = pat.length();
int N = txt.length();
for (int i = 0; i <= N - M; i++){
int j;
for (j = 0; j < M; j++){
if (txt.charAt(i+j) != pat.charAt(j)){
break;
}
}
if (j == M) return i;//Found
}
return N;//Not Found
}
}
蠻力匹配法非常的簡單宛蚓，稍微有編程基礎的人就能夠看懂。
然后是用有限狀態(tài)自動機實現(xiàn)的KMP算法：
public class KMP {
private final int R; // the radix
private int[][] dfa; // the KMP automoton
private String pat; // the pattern string
public static void main(String[] args) {
String pat = args[0];
String txt = args[1];
KMP kmp1 = new KMP(pat);
int offset1 = kmp1.search(txt);
// print results
System.out.println("text: " + txt);
System.out.print("pattern: ");
for (int i = 0; i < offset1; i++)
System.out.print(" ");
System.out.println(pat);
}
public int search(String txt) {
// simulate operation of DFA on text
int m = pat.length();
int n = txt.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == m) return i - m; // found
return n; // not found
}
public KMP(String pat) {
this.R = 256;
this.pat = pat;
// build DFA from pattern
int m = pat.length();
dfa = new int[R][m];
dfa[pat.charAt(0)][0] = 1;
for (int x = 0, j = 1; j < m; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][x]; // Copy mismatch cases.
dfa[pat.charAt(j)][j] = j+1; // Set match case.
x = dfa[pat.charAt(j)][x]; // Update restart state.
}
}
}
可以看到search方法是幾乎一樣的设塔，只不過是加了一個DFA凄吏，現(xiàn)在來看看DFA是怎么運作的：
在這個實現(xiàn)中，默認字母表是ANSSI字符闰蛔，所以DFA中有256個小數組痕钢，ANSSI表中就256個字符，這也暴露了這種實現(xiàn)的一個缺點：如果是中文字母表或者是其他字特別多的表序六，那么需要的空間就太多了任连！
具體講解這個算法非常麻煩，而且塞得威客大大講的非常的好例诀，英語好并且愛聽課的同學可以去看看他的公開課：
Coursera Algorithm Part II
里相關的視頻随抠。
比較喜歡看文字資料的同學可以看一下我啰啰嗦嗦的講解裁着。
KMP算法是怎么做的
我們知道，在蠻力算法中拱她，在匹配的過程中出現(xiàn)了失配的話二驰，就將模式串的指針重置為0，然后將模式串向前移動一位：
仔細觀察這張圖就能發(fā)現(xiàn)椭懊，這樣非常低效诸蚕，我們能夠直觀地看到模式串除了第一個是B之外其他的位置上的字母都是A，在位置六失配氧猬，所以前面一段必然全是A背犯，我們直接把模式串的起始端移動到六位置就可以了，前面的一步一步移動的操作是可以跳過的盅抚，基于這一現(xiàn)象漠魏，深入思考，我們可以發(fā)現(xiàn)妄均，根據模式串的情況柱锹，我們可以推斷出來當在某個位置出現(xiàn)失配的時候我們應該怎么去移動模式串,為什么呢？因為當在六位置失配的時候丰包，我們已經知道了第六位之前的五位是匹配的禁熏，當我們將模式串向前移動一位再進行匹配的時候，相當于讓模式串跟去掉第一個字符并左移一位的自己進行匹配(嚴格來說不是自己邑彪，是自己的一個去掉第一個字符并左移一位的自己的前綴)瞧毙，失配后再重復這個過程。既然是跟自己的一部分匹配寄症，那我們可以在模式串自身進行這個過程并記錄下來各種情況出現(xiàn)的時候該怎么移動宙彪，那么，我們就需要構造一個有限狀態(tài)自動機了有巧。
有限狀態(tài)自動機
有限狀態(tài)自動機是一個很簡單的概念释漆，先簡單看一下它長什么樣子：
先不論代碼是怎么寫的，說一說背后的思想篮迎。
在KMP的字符串匹配的過程中男图，其實就是一個狀態(tài)機的狀態(tài)轉換問題，我們以圖上的狀態(tài)機為例柑潦。
模式串有多長享言，就有多少個狀態(tài)，首先我們是在0狀態(tài)渗鬼，然后開始匹配第一個字符览露，匹配的話，狀態(tài)機進入第二個狀態(tài)譬胎，開始匹配第二個字符差牛，不匹配的話命锄，根據自動機里存儲的轉換方式來轉換狀態(tài)。比如在0狀態(tài)時偏化，被匹配的長字符串的當前字母是A脐恩，那我們就根據dfa[A][0]得到我們應該轉換到1狀態(tài)，然后指向被匹配的字符串的指針進1侦讨。如果被匹配的長字符串的當前字母是B驶冒，那我們就根據dfa[B][0]得到我們應該呆在狀態(tài)0，然后指向被匹配的字符串的指針進1韵卤，然后一步一步地重復這個過程骗污。如果我們前面一直匹配成功的話，我們會成功的從狀態(tài)0一直轉換到狀態(tài)6沈条，當我們的狀態(tài)成功達到6的時候需忿，就說明找到匹配了（注意這個過程中指向被匹配字符串的指針并沒有發(fā)生過回退，我們是通過狀態(tài)的轉換來決定接下來應該從模式字符串的哪一個字符開始與被匹配串的下一個字符進行匹配）蜡歹，匹配結束屋厘。
這個過程非常的簡單直觀，問題在于月而，我們怎樣才能構造出這樣的一個狀態(tài)機汗洒。
我們在這個應用中使用了一個二維數組來代表這個狀態(tài)機，數組的第一個索引是我們在被匹配字符串中所遇到的字符父款，第二個索引是當前自動機所在的狀態(tài)仲翎，在ANSSI字母表中，字符的總數共256個铛漓，所以共有256個子數組，在我們看到的這個案例中鲫构，模式串的長度是6浓恶，所以共有六個狀態(tài)，所以每個子數組的長度是六结笨，代表從0到5六個狀態(tài)包晰。
該怎么構造出這個自動機呢？
過程也非常直觀炕吸，首先我們一眼就能看出來伐憾，當處于零狀態(tài)的時候，如果我們遇到字母A赫模，說明匹配成功树肃，狀態(tài)機的狀態(tài)應該轉向狀態(tài)1，在狀態(tài)1的時候瀑罗，如果遇到了字母B胸嘴，說明匹配再次成功了雏掠，狀態(tài)機的狀態(tài)應該轉換為狀態(tài)2，按照這個思路劣像，我們可以得到在完全匹配情況下的狀態(tài)轉換情況乡话，于是可以在二維數組中寫下這些值。
接下來就是失配狀態(tài)了耳奕，當在狀態(tài)0的時候绑青，如果發(fā)生失配，模式字符串就應該繼續(xù)停留在狀態(tài)0屋群，然后將第0個字符跟被匹配串的下一個字符進行比較闸婴，所以我們可以將dfa[][0]的未匹配位置都初始化為0。
在狀態(tài)1以及以后的狀態(tài)里谓晌，情況就會稍微復雜一些掠拳，但我們可以知道這樣一件事情：如果在第五個字符失配，那我們起碼知道下一次要輸入自動狀態(tài)機的四個字符是啥纸肉，有了這個溺欧，就可以不用回退文本指針了。
我們現(xiàn)在要做的事情是這樣的柏肪，首先用一個指針x指向0狀態(tài)姐刁，然后我們可以直接把0狀態(tài)里的數值直接拷貝到1狀態(tài)，因為當在一狀態(tài)的時候發(fā)生不匹配的時候烦味，我們會用已匹配串的去掉首字母前綴進行匹配聂使，結果是空的，因為此時就一個字母匹配谬俄，然后我們再用不匹配的那個字母跟模式字符串的第一個字母去匹配柏靶，得到模式應該處于的狀態(tài)，所以可以直接將第一個字母的對應的狀態(tài)機的這一列拷貝過來溃论，直接拿到結果屎蜓。然后這個過程是迭代的，也就是說钥勋，當我們在模式串的第三個字符失配的時候楞抡，我們實際上是在拿模式串的第二個字符(因為模式串這時肯定要向前進一)去跟模式串的0狀態(tài)匹配煤裙，然后得到我們用來進行匹配的下一個狀態(tài)喷橙，我們已經通過x = dfa[pat.charAt(j)][x]得到了輸入模式串的第二個字符后自動機的狀態(tài)锣笨，也就是說x現(xiàn)在指向的那一列狀態(tài)就是當前待匹配字符輸入之后應該轉換到的狀態(tài)了(也就是說，在當前位置失配了菲驴，當前位置的文本串應該去跟x位置的模式串字符去做匹配)荐吵，所以我們可以把x指向的那一列直接抄過來。
匹配進狀態(tài)進一，不匹配把去掉首字母已匹配串的的前綴輸入狀態(tài)機(這個操作在構造狀態(tài)機的過程中迭代進行捍靠，沒有重復操作)沐旨，這樣一個狀態(tài)機就構造出來了。
有了這樣一個狀態(tài)機榨婆，在進行模式匹配的時候磁携，我們就可以用j = dfa[txt.charAt(i)][j]; 變換自動機的狀態(tài)，當j等于最后一個狀態(tài)的時候良风，就說明匹配成功了谊迄。
KMP算法就這么煉成了
理解了有限狀態(tài)自動機，KMP算法也就可以很容易地寫出來了烟央，為了練習一下统诺，筆者做了一下leetcode里的編程練習：
字符串匹配
有興趣的同學可以去練習一下加深理解。
后記：反復review加跟各種人解釋疑俭，我特么的把這段代碼背下來了
