当前位置:  编程技术>java/j2ee

JAVA实现KMP算法理论和示例代码

    来源: 互联网  发布时间:2014-10-29

    本文导语:  一.理论准备KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数。整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯...

一.理论准备
KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数。整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯,模式串中部分结果还可以复用,减少了循环次数,提高匹配效率。通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的。例如 主串: abcabcabcabed ,模式串:abcabed。当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位置开始比较直接从模式串的'c'字符开始比较就可以了。并且主串也不用回溯了。
传统的匹配算法没有利用匹配过的信息(模式串是知道的,那么部分匹配主串也是知道的),每次都从头开始比较,速度很慢。
先介绍前缀数组(我自己这么叫的,不知道对不对)是如何产生的。首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
来看一个例子:chi表示模式串的前i个字符组成的前缀, next[i] = j表示chi中的开始j个字符和末尾j个字符是一样的(注意下标是字符数目),而且对于前缀chi来说,这样的j是最大值。next[i] = j的另外一个定义是:有一个含有j个字符的串,它既是chi的真前缀,又是chi的真后缀。
 规定:next[1] = next[0] = 0,这个规定不像0!=1那样,而是确实是这样子,不懂得看上面的前后缀概念。注意:next数组里并不是首尾回文串,而是前缀等于后缀,理解这个对于递推求next数组很重要哟。next[i]就是前缀数组,下面通过1个例子来看如何构造前缀数组。
 例:cacca有5个前缀,求出其对应的next数组。前缀2为ca,显然首尾没有相同的字符,next[2] = 0,前缀3为cac,显然首尾有共同的字符c,故next[3] = 1,前缀4为cacc,首尾有共同的字符c,故next[4] = 1,前缀5为cacca,首尾有共同的字符ca,故next[5] = 2。如果仔细观察,可以发现构造next[i]的时候,可以利用next[i-1]的结果。比如abcdabc,模式已求得next[7] = 3,为求next[8],可以直接比较第4个字符和第8个字符,如果它们相等,则next[8] = next[7]+1 = 4,这是因为next[7] = 3保证了前缀ch7的末尾4个字符的前3个字符是一样的。但如果这两个字符不想等呢?那就继续迭代,利用(k=3)k = next[k]的值来求,直到k=0(next[8] = 0)或者字符相等(next[8] = k+1)。
二.算法实现
代码如下:

import java.util.ArrayList;
public class KMP {
 //主串
 static String str = "1kk23789456789hahha";
 //模式串
 static String ch = "789";
 static int next[] = new int[20];

 public static void main(String[] args) {
  setNext();
  ArrayList arr = getKmp();
  if(arr.size()!=0) {
   for(int i=0; i

    
 
 

您可能感兴趣的文章:

  • andriod下java socket网络编程:java socket客户端服务端代码示例
  • 输出java进程的jstack信息示例分享 通过线程堆栈信息分析java线程
  • java Servlet实现Session创建存取以及url重写代码示例
  • java 四舍五入使java保留2位小数示例讲解
  • java进行error捕获和处理示例(java异常捕获)
  • java去除集合中重复元素示例分享 java去除重复
  • java读取csv文件示例分享(java解析csv文件)
  • java求三个数的最大值的示例分享
  • java生成字母数字组合的随机数示例 java生成随机数
  • java实现网页解析示例
  • java协变返回类型使用示例
  • 使用java执行定时任务示例
  • java自定义枚举转换器示例
  • java向文件末尾添加内容示例分享
  • java正则表达式获取url的host示例
  • java使用正则表达校验手机号码示例(手机号码正则)
  • java实现jframe透明窗体示例
  • java的split方法使用示例
  • java抓取网页数据示例
  • Oracle 使用Java Source 简单示例
  • java自定义日期转化类示例
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • java分析html算法(java网页蜘蛛算法示例)
  • 哪里有 DES 算法的Java原码?
  • JAVA有用于数据校验的类吗?象加密算法那样的.
  • Java算法工具 NA_WorkSheet
  • 寻求java加密算法及实例
  • java异或加密算法
  • Java算法包 jga
  • 哪里有《数据结构与算法分析(JAVA版)》的电子书下载,谢了:)
  • 谁给一个树的算法(JAVA)给我?
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 考个SUN的JAVA认证值不值?能学到东西吗?是理论知识还是实践知识
  • java命名空间java.sql类types的类成员方法: java_object定义及介绍
  • 我想学JAVA ,是买THINK IN JAVA 还是JAVA2核心技术:卷1 好???
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: imageflavor定义及介绍
  • 请问Java高手,Java的优势在那里??,Java主要适合于开发哪类应用程序
  • java命名空间java.lang.management类managementfactory的类成员方法: getcompilationmxbean定义及介绍
  • 如何将java.util.Date转化为java.sql.Date?数据库中Date类型对应于java的哪个Date呢
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getlibrarypath定义及介绍
  • 谁有电子版的《Java编程思想第二版(Thinking in java second)》和《Java2编程详解(special edition java2)》?得到给分
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getstarttime定义及介绍
  • 本人想学java,请问java程序员的待遇如何,和java主要有几个比较强的方向
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: stringflavor定义及介绍
  • 我对JAVA一窍不通,可惜别人却给我一个Java的project,要我做一个安装程序,请问哪里有JAVA INSTALLER下载,而且我要不要安装java的sdk才能完成此项任务?
  • java命名空间java.security类keystore的类成员方法: getdefaulttype定义及介绍
  • 新年第一天,让我们讨论一下未来一年JAVA的发展趋势! 个人认为,JAVA将主要朝ERP和JAVA手机方面发展!
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getclasspath定义及介绍
  • 我想学Java,但不知道Java的实用的开发工具有那些,Java主要用在哪些方面,EJB到底是什么东西??
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: javaserializedobjectmimetype定义及介绍
  • redhat7.3下,java程序打印中文直接用java命令执行正常,用crontab执行java命令为乱码
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: javafilelistflavor定义及介绍
  • 各位学java的朋友,学java的未来是什么,你们学java都用来开发什么项目啊!来者给分!!
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getvmname定义及介绍
  • 请问java程序中的import为什么有的用java.….*,而有的又用java.….…,有什么区别吗?




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3