一.理論准備
KMP算法為什麼比傳統的字符串匹配算法快？KMP算法是通過分析模式串，預先計算每個位置發生不匹配的時候，可以省去重新匹配的的字符個數。整理出來發到一個next數組， 然後進行比較，這樣可以避免字串的回溯，模式串中部分結果還可以復用，減少了循環次數，提高匹配效率。通俗的說就是KMP算法主要利用模式串某些字符與模式串開頭位置的字符一樣避免這些位置的重復比較的。例如 主串： abcabcabcabed ,模式串：abcabed。當比較到模式串'e'字符時不同的時候完全沒有必要從模式串開始位置開始比較直接從模式串的'c'字符開始比較就可以了。並且主串也不用回溯了。
傳統的匹配算法沒有利用匹配過的信息(模式串是知道的，那麼部分匹配主串也是知道的)，每次都從頭開始比較，速度很慢。
先介紹前綴數組(我自己這麼叫的，不知道對不對)是如何產生的。首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字符以外，一個字符串的全部頭部組合；"後綴"指除了第一個字符以外，一個字符串的全部尾部組合。
來看一個例子：chi表示模式串的前i個字符組成的前綴， next[i] = j表示chi中的開始j個字符和末尾j個字符是一樣的(注意下標是字符數目)，而且對於前綴chi來說，這樣的j是最大值。next[i] = j的另外一個定義是：有一個含有j個字符的串，它既是chi的真前綴，又是chi的真後綴。
規定：next[1] = next[0] = 0，這個規定不像0！=1那樣，而是確實是這樣子，不懂得看上面的前後綴概念。注意：next數組裡並不是首尾回文串，而是前綴等於後綴，理解這個對於遞推求next數組很重要喲。next[i]就是前綴數組，下面通過1個例子來看如何構造前綴數組。
例：cacca有5個前綴，求出其對應的next數組。前綴2為ca，顯然首尾沒有相同的字符，next[2] = 0，前綴3為cac，顯然首尾有共同的字符c，故next[3] = 1，前綴4為cacc，首尾有共同的字符c，故next[4] = 1，前綴5為cacca，首尾有共同的字符ca，故next[5] = 2。如果仔細觀察，可以發現構造next[i]的時候，可以利用next[i-1]的結果。比如abcdabc，模式已求得next[7] = 3，為求next[8]，可以直接比較第4個字符和第8個字符，如果它們相等，則next[8] = next[7]+1 = 4，這是因為next[7] = 3保證了前綴ch7的末尾4個字符的前3個字符是一樣的。但如果這兩個字符不想等呢？那就繼續迭代，利用(k=3)k = next[k]的值來求,直到k=0(next[8] = 0)或者字符相等(next[8] = k+1)。
二.算法實現
代碼如下：
import java.util.ArrayList;
public class KMP {
//主串
static String str = "1kk23789456789hahha";
//模式串
static String ch = "789";
static int next[] = new int[20];
public static void main(String[] args) {
setNext();
ArrayList<Integer> arr = getKmp();
if(arr.size()!=0) {
for(int i=0; i<arr.size(); i++) {
System.out.println("匹配發生在:"+arr.get(i));
}
}else {
System.out.println("匹配不成功");
}
}
private static void setNext() {
// TODO Auto-generated method stub
int lenCh = ch.length();
next[0] = 0;
next[1] = 1;
//k表示next[i-1]的值
int k = 0;
for(int i=2; i<=lenCh; i++) {
k = next[k];
/*
* 這個while循環的作用找個例子看看就好理解了
* 我認為是每次找最長，一旦成功就停止，保證找到的是當前最長
*/
while(k!=0 && ch.charAt(i-1)!=ch.charAt(k)) {
k = next[k];
}
if(ch.charAt(i-1)==ch.charAt(k)) {
k++;
}//else就是k=0
//不是next[k] = k，i表示有幾個字符的前綴
next[i] = k;
}
}
private static ArrayList<Integer> getKmp() {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>();
int lenStr = str.length();
int lenCh = ch.length();
//主串開始的匹配位置
int pos = 0;
//模式串每次匹配位置
int k = 0;
//循環條件不是k<lenCh,這樣的話可能死循環(沒有匹配發生)
while(pos<lenStr) {
/*
* 首次進入沒什麼大作用，做要是為提高以後的匹配效率
* 寫在最後一行也行
*/
k = next[k];
while(k<lenCh && str.charAt(pos)==ch.charAt(k)) {
pos++;
k++;
}
if(lenCh==k) {
arr.add(pos-k);
}else if(0==k) {
/*
* 不加這一句死循環
* 因為next[0] = 0
* 比如abcd和abce，到de不匹配，此時執行k = next[k](k=3),
* k變為0，發現d和a不匹配，此時k還是0，重復執行以上步驟，那麼死循環了
*/
pos++;
}//實際上else就是k = next[k]，所以才說k = next[k]寫在最後一行也行
}
return arr;
}
}
三.問題擴展
KMP算法的高效性往往是在模式串比較長的時候才能體現出來(看next數組的推導過程)，而實際上模式串往往很短，回想自己使用辦公套件時查找的字符串長度，所以實踐上大多使用BM算法來實現，感興趣的讀者可以自己查閱相關資料，或許可以再看看多模匹配(在主串中一次查找多個模式串)的AC自動機、dictmatch算法。
