如何通过Java代码实现KMP算法

这篇文章主要介绍了如何通过Java代码实现KMP算法,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，

函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

代码如下

import java.util.Arrays;

public class Test {

  /**
   * @param str 文本串
   * @param dest 模式串
   * @param next 匹配核心数组
   * @return
   */
  public static int kmp(String str, String dest,int[] next) {
    for(int i = 0, j = 0; i < str.length(); i++){
      if (j > 0 && str.charAt(i) != dest.charAt(j)) {
        j = next[j - 1];
      }
      if (str.charAt(i) == dest.charAt(j)) {
        j++;
      }
      if (j == dest.length()) {
        return i-j+1;
      }
    }
    return 0;
  }

  public static int[] kmpnext(String dest) {
    int[] next = new int[dest.length()];
    next[0] = 0;
    for(int i = 1,j = 0; i < dest.length(); i++) {
      if (j > 0 && dest.charAt(j) != dest.charAt(i)) {
        j = next[j - 1];
      }
      if (dest.charAt(i) == dest.charAt(j)) {
        j++;
      }
      next[i] = j;
    }
    return next;
  }

  public static void main(String[] args){
    String a = "ABABAE";
    String b = "ABABABABAEBEABADAEABAEABABAE";
    int[] next = kmpnext(a);
    System.out.println(Arrays.toString(next));
    int res = kmp(b, a,next);
    System.out.println(res);
  }

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java获得一个数组的指定长度排列组合算法示例

    本文实例讲述了Java获得一个数组的指定长度排列组合算法.分享给大家供大家参考,具体如下: package demo; import java.util.Stack; /** * JAVA获得一个数组的指定长度的排列组合.<br> * * @author JAVA世纪网(java2000.net, laozizhu.com) */ public class TestSequenceAll { public static void main(String[] args) { TestSequen

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

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

    一.理论准备KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数.整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯,模式串中部分结果还可以复用,减少了循环次数,提高匹配效率.通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的.例如 主串: abcabcabcabed ,模式串:abcabed.当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位

  • Java基于深度优先遍历的随机迷宫生成算法

    Java基于深度优先遍历的随机迷宫生成算法

    这两天因为要做一个随机的地图生成系统,所以一直在研究随机迷宫生成算法,好吧,算是有一点小小的成果. 随机迷宫生成我自己的理解简而言之分为以下几步: 1.建立一张地图,我用的二维数组表示,地图上全是障碍物.然后再创建一个用来表示每个格子是否被访问过的二维数组.再创建一个用来表示路径的栈结构. 2.随机选择地图上的一点,呃为了方便我初始点直接取的是左上角即坐标表示为0,0的格子.终点的话因为不涉及到交互就暂时没有. 3.查找当前格子的邻接格(注意,这里的邻接格子都是还未被访问的,下面的代码里有写).

  • Java求质数的几种常用算法分析

    本文实例讲述了Java求质数的几种常用算法.分享给大家供大家参考,具体如下: 1.根据质数的定义求 质数定义:只能被1或者自身整除的自然数(不包括1),称为质数. 利用它的定义可以循环判断该数除以比它小的每个自然数(大于1),如果有能被它整除的,则它就不是质数. 对应代码是: void printPrime(int n){//判断n是否是质数 boolean isPrime=true;//是否是质数的标志 for(int i=n-1;i>1;i-){//n除以每个比n小比1大的自然数 if(n%

  • Java实现的数字签名算法RSA完整示例

    本文实例讲述了Java实现的数字签名算法RSA.分享给大家供大家参考,具体如下: 一 背景介绍 数字签名:带有密钥(公钥.私钥)的消息摘要算法. 验证数据完整性.认证数据来源.抗否认. 私钥签名.公钥验证. 常用算法:RSA.DSA.ECDSA 二 RSA介绍 包括MD和SHA两类 三 Java代码实现 package com.imooc.security.rsa2; import java.security.KeyFactory; import java.security.KeyPair; i

  • java短网址服务(TinyURL)生成算法

    java短网址服务(TinyURL)生成算法

    前不久做了一个优惠劵的分享功能,其中一个功能就是生成一个优惠劵分享短链接.生成的短链接要求每个链接都是唯一的,并且长度尽可能短.在网上查了一下相关的思路,发现了一个不错的算法.这个算法的思路就是用[a-zA-Z0-9]建立一个长度为62的矩阵,然后把矩阵打乱,再生成一个全局唯一的数字,再把这个数字用矩阵内的元素表示转换成62进制,生成的链接长度最大才11位.所以短链接的生成关键点就变成了如何生成一个全局唯一的数字和实现进制的转换. 1.生成全局唯一的数字 这本质是一个分布式ID的问题.如果简单处

  • 如何通过Java代码实现KMP算法

    这篇文章主要介绍了如何通过Java代码实现KMP算法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法).KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是实现一个next()函数, 函数本身包含了模式串的局部匹配信息.时间复

  • Java数据结构之KMP算法详解以及代码实现

    目录 暴力匹配算法(Brute-Force,BF) 概念和原理 next数组 KMP匹配 KMP全匹配 总结 我们此前学了前缀树Trie的实现原理以及Java代码的实现.Trie树很好,但是它只能基于前缀匹配实现功能.但是如果我们的需求是:一个已知字符串中查找子串,并且子串并不一定符合前缀匹配,那么此时Trie树就无能为力了. 实际上这种字符串匹配的需求,在开发中非常常见,例如判断一个字符串是否包括某些子串,然后进行分别的处理. 暴力匹配算法(Brute-Force,BF) 这是最常见的算法字符

  • Java数据结构彻底理解关于KMP算法

    Java数据结构彻底理解关于KMP算法

    大家好,前面的有一篇文章讲了子序列和全排列问题,今天我们再来看一个比较有难度的问题.那就是大名鼎鼎的KMP算法. 本期文章源码:GitHub源码 简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息.KMP算法

  • java 实现KMP算法

    java 实现KMP算法

    KMP算法是一种神奇的字符串匹配算法,在对 超长字符串 进行模板匹配的时候比暴力匹配法的效率会高不少.接下来我们从思路入手理解KMP算法. 在对字符串进行匹配的时候我们最容易想到的就是一个个匹配,类似下面这种: 换成Java代码就是: public static boolean bfSearch(String pattern,String txt){ if (txt.length() < pattern.length()) return false; for (int i = 0; i < t

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • 详解Java中KMP算法的图解与实现

    详解Java中KMP算法的图解与实现

    目录 图解 代码实现 图解 kmp算法跟之前讲的bm算法思想有一定的相似性.之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子. 观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可. 那如果好前缀中有互相匹配的字符呢? 观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串.那我们如何根据好前缀来进行合理滑动? 其实就是看当前的好前缀的前缀和后缀

  • KMP算法精解及其Python版的代码示例

    KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式

  • Java代码实践12306售票算法(二)

    Java代码实践12306售票算法(二)

    周五闲来无事,基于上一篇关于浅析12306售票算法(java版)理论,进行了java编码实践供各位读者参考(以下为相关代码的简单描述) 1.订票工具类 1.1初始化一列车厢的票据信息 /** * 生成Ticket信息 * * @param train * @return */ public static List<Ticket> initTicketList(Train train) { List<Ticket> result = new ArrayList<Ticket&g

随机推荐