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
相关文档：
今天和大家一起学习Java的设计模式。本人的水平不是很高，这系列文章只是自己学习的过程，并希望能同大家分享经验。
先说下我对工厂模式的理解：当我们需要某个对象时，最直接的办法是看到这个对象就拿过来。但是当对象非常多的时候，找起来就很不方便。这时就需要一个中介来帮助我们取得想要的东西，这个中介就是工厂（fa ......
方法的重载
：同一个类里面方法的名字相同，方法的参数项（主要是参数类型，参数个数）
不同
,
返回类型可能不同。
重载方法可以具有不同的返回类型，但返回类型本身不足以区分方法的两个版
本。 ......
一、什么是反射：
反射的概念是由Smith在1982年首次提出的，主要是指程序可以访问、检测和修改它本身状态或行为的一种能力。这一概念的提出很快引发了计算机科学领域关于应用反射性的研究。它首先被程序语言的设计领域所采用,并在Lisp和面向对象方面取得了成绩。其中LEAD/LEAD++ 、OpenC++ 、MetaXa和OpenJava等就是基于反 ......
Java学习路线
先学习j2se
要学习j2ee就要先学习j2se，刚开始学习j2se先建议不要使用IDE，然后渐渐的过渡到使用IDE开发，毕竟用它方便嘛。学习j2se推荐两本书，《java2核心技术一二卷》，《java编程思想》，《java模式》。其中《java编程思想》要研读，精读。这一段时间是基本功学习，时间会很长，也可能很短，这要看学� ......
Java执行stm.executeQuery(sql); 时总是提示：java.sql.SQLException: ORA-00911: 无效字符，弄了半天还是出错，无奈，拿出杀手锏，Google一下，晕倒，发现我的String sql = “select detail from test.result where person_id = 4; "，貌似没错误吧，结果我我必须去掉最后分号，本来是想搞得专业点，就价加个分 ......
