在介紹kmp算法之前仔掸，我想先簡單介紹一下Brute-Force算法憔儿，這是一個回溯的字符串模式匹配算法赠堵，是一個簡單暴力狂！
由上圖的匹配思想法褥，主要代碼如下：
public static int indexOf(String target, String pattern){
int i = 0,j = 0;
while(i < target.length() - pattern.length()){
if(target.charAt(i+j) == pattern.charAt(j)){
j++;
}else{
i++;
j = 0;
}
if(j == pattern.length()){
return i;
}
}
return -1;
}
很明顯茫叭，當(dāng)匹配不成功時，目標串每次向前移動一位半等，模式串每次從P0開始重新匹配揍愁，雙方都存在回溯現(xiàn)象。在上圖中可以看出最差的情況： 每次匹配比較M次杀饵，比較了N - M + 1 次莽囤，比較總數(shù)是 M*(N - M + 1)，由于M << N切距，所以時間復(fù)雜度O(M * N) 朽缎。
下面分析下Brute-Force算法的缺點：
下面就著重講一下KMP算法：
-
算法描述：
核心是找到模式串中的k( 0 <=k < j) 滿足"P0...Pk-1" = "Pj-k...Pj-1" = "Ti-k...Ti-1" (當(dāng)Pj != Ti時)庆杜，則模式串從Pk開始遍歷薄翅。
所以問題就轉(zhuǎn)化為：找到串"P0...Pj-1"相同的前綴子串和后綴子串的長度k。
- 求next數(shù)組
根據(jù)上圖的模式串"abcabc"蜡峰，可以得到next數(shù)組(注意在"P0...Pj-1"中尋找)
| j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 模式串 | a | b | c | a | b | c |
| next[j] | -1 | 0 | 0 | 0 | 1 | 2 |
- 計算next數(shù)組的算法
由next數(shù)組的定義可以：
- next[0] = -1;
- 2.對于任意的j (0<=j <m ) next[j] < j;
- 若next[j] = k 說明在子串"P0...Pj-1"中存在相同的前綴子串和后綴子串葡幸，"P0...Pk-1" = "Pj-k...Pj-1" (0=<k<j最筒，k取最大值)；
- 對于next[j+1]而言蔚叨，判斷"P0...Pj"子串中床蜘，是否存在"P0...Pk" = "Pj-k...Pj-1Pj"的問題辙培，可以分解為 ：
- 是否存在"P0...Pk-1" = "Pj-k...Pj-1"的問題；
- Pk == Pj的問題邢锯；
- 對于next[j+1]而言蔚叨，判斷"P0...Pj"子串中床蜘，是否存在"P0...Pk" = "Pj-k...Pj-1Pj"的問題辙培，可以分解為 ：
很符合動態(tài)規(guī)劃(Dynamic Programming)的問題扬蕊，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系弹囚，逐個求解厨相，很像分治法。
同時個人認為很像高考數(shù)列的相關(guān)問題 ---- 數(shù)學(xué)歸納法鸥鹉。
某個數(shù)列 An
- An = K (常數(shù))蛮穿；
- 假設(shè)前N項滿足： An = f(n) (某個函數(shù)式)；
- 如果第N+1項 滿足 An+1 = f(n+1)毁渗，則An = f(n) 等式成立践磅。
綜上所述該動態(tài)規(guī)劃的遞推公式：
D(j+1) = max(D(j)) + (Pk == Pj ? 1 : 0)
- 改進next數(shù)組
在上圖1-3中 Pk = Pj , Ti != Pj => Pk != Ti 則完全沒有必要回溯到Pk開始比較，直接從P0開始灸异，所以假如next[j] = k 且 Pk = Pj 則 next[j] = next[k];
- KMP核心代碼
private static int[] getNext(String pattern){
int j = 0,k = -1;
int[] next = new int[pattern.length()];
next[0] = -1;
while(j < pattern.length() - 1){
if(k == -1 || pattern.charAt(j) == pattern.charAt(k)){
j++;
k++;
//改進next數(shù)組
if(pattern.charAt(j) != pattern.charAt(k)){
next[j] = k;
}else{
next[j] = next[k];
}
}else{
k = next[k];
}
}
return next;
}
public static int indexOf(String target, String pattern){
int i = 0,j = 0;
int[] next = getNext(pattern);
while(i < target.length()){
if(j == -1 || target.charAt(i) == pattern.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
if(j == pattern.length()){
return i - j;
}
}
return -1;
}
- KMP算法分析
時間復(fù)雜度O(M + N) 府适，當(dāng)M<<N或者比較次數(shù)少（匹配的成功率比較高），時間復(fù)雜度O(N)肺樟。
以上是本人對KMP算法的理解檐春，歡迎大家指正和交流，謝謝么伯！
