源代碼：

package algorithm.kmp;

/**
 * KMP算法的Java實(shí)現(xiàn)例子與測(cè)試、分析
 * @author zuoliuhongxiang
 * @date 2009-3-25
 */
public class KMP {
 /**
  * 對(duì)子串加以預(yù)處理，從而找到匹配失敗時(shí)子串回退的位置
  * 找到匹配失敗時(shí)的最合適的回退位置，而不是回退到子串的第一個(gè)字符，即可提高查找的效率
  * 因此為了找到這個(gè)合適的位置，先對(duì)子串預(yù)處理，從而得到一個(gè)回退位置的數(shù)組
  * @param B，待查找子串的char數(shù)組
  * @return
  */
 public static int[] preProcess(char [] B) {
  int size = B.length;
  int[] P = new int[size];
  P[0]=0;
  int j=0;
  //每循環(huán)一次，就會(huì)找到一個(gè)回退位置
  for(int i=1;i<size;i++){
   //當(dāng)找到第一個(gè)匹配的字符時(shí)，即j>0時(shí)才會(huì)執(zhí)行這個(gè)循環(huán)
   //或者說(shuō)p2中的j++會(huì)在p1之前執(zhí)行（限于第一次執(zhí)行的條件下）
   //p1
   while(j>0 && B[j]!=B[i]){
    j=P[j];
   }
   //p2，由此可以看出，只有當(dāng)子串中含有重復(fù)字符時(shí)，回退的位置才會(huì)被優(yōu)化
   if(B[j]==B[i]){
    j++;
   }
   //找到一個(gè)回退位置j，把其放入P[i]中
   P[i]=j;
  }
  return P;
 }
 
 /**
  * KMP實(shí)現(xiàn)
  * @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++){
   //當(dāng)找到第一個(gè)匹配的字符時(shí)，即j>0時(shí)才會(huì)執(zhí)行這個(gè)循環(huán)
   //或者說(shuō)p2中的j++會(huì)在p1之前執(zhí)行（限于第一次執(zhí)行的條件下）
   //p1
   while(j>0 && B[j]!=A[i]){
    //找到合適的回退位置
    j=P[j-1];
   }
   //p2 找到一個(gè)匹配的字符
   if(B[j]==A[i]){
    j++;
   }
   //輸出匹配結(jié)果，并且讓比較繼續(xù)下去
   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) {
  //回退位置數(shù)組為P[0, 0, 0, 0, 0, 0]
  kmp("abcdeg, abcdeh, abcdef!這個(gè)會(huì)匹配1次","abcdef");
  //回退位置數(shù)組為P[0, 0, 1, 2, 3, 4]
  kmp("Test ititi ititit! Test ititit!這個(gè)會(huì)匹配2次","ititit");
  //回退位置數(shù)組為P[0, 0, 0]
  kmp("測(cè)試漢字的匹配，左劉鴻翔。這個(gè)會(huì)匹配1次","左劉鴻翔");
  //回退位置數(shù)組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
  kmp("這個(gè)會(huì)匹配0次","it1it1it1");
 }
}

輸出結(jié)果：

Find subString 'abcdef' at 16
Totally found 1 times for 'abcdef'.

Find subString 'ititit' at 11
Find subString 'ititit' at 24
Totally found 2 times for 'ititit'.

Find subString '左劉鴻翔' at 8
Totally found 1 times for '左劉鴻翔'.

Totally found 0 times for 'it1it1it1'.


結(jié)論：

通過(guò)找到合適的回退位置從而可以提高匹配效率。