KMP算法的Java實現例子以及測試分析

2019-11-17 04:17:45

字體：大中小

來源：轉載

供稿：網友

背景簡介：KMP算法用來處理字符串匹配的。給你A,B兩個字符串，檢查B串是否是A串的子串，類似于java的String.indexOf("")。之所以叫做KMP，是因為這個算法是由Knuth、Morris、PRatt三個提出來的，取了這三個人的名字的頭一個字母。

原理介紹：找到匹配失敗時的最合適的回退位置，而不是簡單的回退到子串的第一個字符（常規的枚舉查找方式，是簡單的回退到子串的第一個字符，接下來準備寫一篇KMP算法的性能分析Java實現實例），即可提高查找的效率。因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數組。過多的理論就不介紹了。

總體而言比較簡單，KMP算一個經典的算法例子，很多筆試、面試也會問起。現總結一下，放在這里供大家參考、交流，希望對大家有所幫助，下面直接給出實現例子，測試與分析也包含其中。

一、一個文件源代碼

KMP.java

源代碼為：

package algorithm.kmp;

/**
* KMP算法的Java實現例子與測試、分析
* @author 崔衛兵
* @date 2009-3-25
*/
public class KMP {
/**
* 對子串加以預處理，從而找到匹配失敗時子串回退的位置
* 找到匹配失敗時的最合適的回退位置，而不是回退到子串的第一個字符，即可提高查找的效率
* 因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數組
* @param B，待查找子串的char數組
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循環一次，就會找到一個回退位置
for(int i=1;i<size;i++){
   //當找到第一個匹配的字符時，即j>0時才會執行這個循環
   //或者說p2中的j++會在p1之前執行（限于第一次執行的條件下）
   //p1
   while(j>0 && B[j]!=B[i]){
    j=P[j];
   }
   //p2，由此可以看出，只有當子串中含有重復字符時，回退的位置才會被優化
   if(B[j]==B[i]){
    j++;
   }
   //找到一個回退位置j，把其放入P[i]中
   P[i]=j;
}
return P;
}

/**
* KMP實現
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
   //當找到第一個匹配的字符時，即j>0時才會執行這個循環
   //或者說p2中的j++會在p1之前執行（限于第一次執行的條件下）
   //p1
   while(j>0 && B[j]!=A[i]){
    //找到合適的回退位置
    j=P[j-1];
   }
   //p2 找到一個匹配的字符
   if(B[j]==A[i]){
    j++;
   }
   //輸出匹配結果，并且讓比較繼續下去
   if(j==subSize){
    j=P[j-1];
    k++;
    System.out.printf("Find subString '%s' at %d/n",subStr,i-subSize+1);
   }
}
System.out.printf("Totally found %d times for '%s'./n/n",k,subStr);
}

public static void main(String[] args) {
//回退位置數組為P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!這個會匹配1次","abcdef");
//回退位置數組為P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!這個會匹配2次","ititit");
//回退位置數組為P[0, 0, 0]
kmp("測試漢字的匹配，崔衛兵。這個會匹配1次","崔衛兵");
//回退位置數組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("這個會匹配0次","it1it1it1");
}
}