易截截图软件、单文件、免安装、纯绿色、仅160KB

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 transient 关键字

transient是Java语言的关键字,用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候,transient型变量的值不包括在串行化的表示中,然而非transient型的变量是被包括进去的!
public class User implements Serializable{
private static final long serialVersionUID = 1L;


private Integer id; ......

Java 复习笔记_第1天

 
方法的重载
:同一个类里面方法的名字相同,方法的参数项(主要是参数类型,参数个数)
不同
,
返回类型可能不同。
      
  
        
重载方法可以具有不同的返回类型,但返回类型本身不足以区分方法的两个版
本。 ......

java文件过滤器的使用

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())) {
   ......

java抽象类和抽象方法

抽象类就是不能使用new方法进行实例化的类,即没有具体实例对象的类。抽象类有点类似“模板”的作用,目的是根据其格式来创建和修改新的类。对象不能由抽象类直接创建,只可以通过抽象类派生出新的子类,再由其子类来创建对象。当一个类被声明为抽象类时,要在这个类前面加上修饰符abstract。
  &nbs ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号