KMP算法的Java实现例子以及测试分析

背景简介：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;
&n