易截截图软件、单文件、免安装、纯绿色、仅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设计模式系列教程(一)工厂模式factory

今天和大家一起学习Java的设计模式。本人的水平不是很高,这系列文章只是自己学习的过程,并希望能同大家分享经验。
先说下我对工厂模式的理解:当我们需要某个对象时,最直接的办法是看到这个对象就拿过来。但是当对象非常多的时候,找起来就很不方便。这时就需要一个中介来帮助我们取得想要的东西,这个中介就是工厂(fa ......

java中的反射机制

一、什么是反射:
反射的概念是由Smith在1982年首次提出的,主要是指程序可以访问、检测和修改它本身状态或行为的一种能力。这一概念的提出很快引发了计算机科学领域关于应用反射性的研究。它首先被程序语言的设计领域所采用,并在Lisp和面向对象方面取得了成绩。其中LEAD/LEAD++ 、OpenC++ 、MetaXa和OpenJava等就是基于反 ......

Java Scanner NoSuchElementException

今天同学问我一个Java问题,代码结构如下:
Scanner scan = new Scanner(System.in);
scan.next();
scan.close();
scan = new Scanner(System.in);
scan.next(); 
当程序运行到第五行是会抛出java.util.NoSuchElementException
          at&nb ......

Java连接Oracle问题

Java执行stm.executeQuery(sql); 时总是提示:java.sql.SQLException: ORA-00911: 无效字符,弄了半天还是出错,无奈,拿出杀手锏,Google一下,晕倒,发现我的String  sql = “select detail from test.result where person_id = 4; ",貌似没错误吧,结果我我必须去掉最后分号,本来是想搞得专业点,就价加个分 ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号