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
相关文档:
transient是Java语言的关键字,用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候,transient型变量的值不包括在串行化的表示中,然而非transient型的变量是被包括进去的!
public class User implements Serializable{
private static final long serialVersionUID = 1L;
private Integer id;
......
方法的重载
:同一个类里面方法的名字相同,方法的参数项(主要是参数类型,参数个数)
不同
,
返回类型可能不同。
重载方法可以具有不同的返回类型,但返回类型本身不足以区分方法的两个版
本。 ......
java文件过滤器的使用代码如下:
测试代码:package file;
import java.io.File;
public class fileFilter {
public static void main(String[] args) {
File file = new File("d:\\");//设置文件路径
for (File fileList : file.listFiles(new file.MyFileFilter())) {
......
抽象类就是不能使用new方法进行实例化的类,即没有具体实例对象的类。抽象类有点类似“模板”的作用,目的是根据其格式来创建和修改新的类。对象不能由抽象类直接创建,只可以通过抽象类派生出新的子类,再由其子类来创建对象。当一个类被声明为抽象类时,要在这个类前面加上修饰符abstract。
&nbs ......