JAVA实现KMP算法理论和示例代码
发布时间:2021-08-06 07:13:44
一.理论准备
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<Integer> arr = getKmp();
if(arr.size()!=0) {
for(int i=0; i<arr.size(); i++) {
System.out.println("匹配发生在:"+arr.get(i));
}
}else {
System.out.println("匹配不成功");
}
}
private static void setNext() {
// TODO Auto-generated method stub
int lenCh = ch.length();
next[0] = 0;
next[1] = 1;
//k表示next[i-1]的值
int k = 0;
for(int i=2; i<=lenCh; i++) {
k = next[k];
/*
* 这个while循环的作用找个例子看看就好理解了
* 我认为是每次找最长,一旦成功就停止,保证找到的是当前最长
*/
while(k!=0 && ch.charAt(i-1)!=ch.charAt(k)) {
k = next[k];
}
if(ch.charAt(i-1)==ch.charAt(k)) {
k++;
}//else就是k=0
//不是next[k] = k,i表示有几个字符的前缀
next[i] = k;
}
}
private static ArrayList<Integer> getKmp() {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>();
int lenStr = str.length();
int lenCh = ch.length();
//主串开始的匹配位置
int pos = 0;
//模式串每次匹配位置
int k = 0;
//循环条件不是k<lenCh,这样的话可能死循环(没有匹配发生)
while(pos<lenStr) {
/*
* 首次进入没什么大作用,做要是为提高以后的匹配效率
* 写在最后一行也行
*/
k = next[k];
while(k<lenCh && str.charAt(pos)==ch.charAt(k)) {
pos++;
k++;
}
if(lenCh==k) {
arr.add(pos-k);
}else if(0==k) {
/*
* 不加这一句死循环
* 因为next[0] = 0
* 比如abcd和abce,到de不匹配,此时执行k = next[k](k=3),
* k变为0,发现d和a不匹配,此时k还是0,重复执行以上步骤,那么死循环了
*/
pos++;
}//实际上else就是k = next[k],所以才说k = next[k]写在最后一行也行
}
return arr;
}
}
三.问题扩展
KMP算法的高效性往往是在模式串比较长的时候才能体现出来(看next数组的推导过程),而实际上模式串往往很短,回想自己使用办公套件时查找的字符串长度,所以实践上大多使用BM算法来实现,感兴趣的读者可以自己查阅相关资料,或许可以再看看多模匹配(在主串中一次查找多个模式串)的AC自动机、dictmatch算法。
猜你喜欢
- Android指定SnackBar在屏幕的位置Snackbar 常以一个小的弹出框的形式,出现在手机屏幕下方或者桌面左下方,并且是在屏幕所有
- 简介Spring Security,这是一种基于 Spring AOP 和 Servlet 过滤器的安全框架。它提供全面的安全性解决方案,同
- 1 框架组成SpringSpringMVCMyBatis2 所需工具Mysql 8.0.15数据库管理系统,创建数据库Tomcat 8.5.
- 一. 为什么要使用接口假如有一个需求:要求实现防盗门的功能。门有"开"和"关"的功能,锁有"
- 获取自定义菜单查询返回的结果有乱码解决方法:string Posturl = "https://api.weixin.qq.com
- 很多时候我们开发的软件需要向用户提供软件参数设置功能,例如我们常用的QQ,用户可以设置是否允许陌生人添加自己为好友。对于软件配置参数的保存,
- Object是所有类的父类,也就是说java中所有的类都是直接或者间接继承自Object类。比如你随便创建一个classA,虽然没有明说,但
- 一、结论先行ArrayList在JDK1.8与JDK1.7底层区别JDK1.7:ArrayList像饿汉式,直接创建一个初始容量为10的数组
- 今天我们介绍的是jpa删除和事务的一些坑,接下来看看具体内容。业务场景(这是一个在线考试系统)和代码:根据问题的id删除答案reposito
- 以下代码为一个工具类package com.imooc.reflect;import java.lang.reflect.Method;pu
- mybatis在持久层框架中还是比较火的,一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库,很是灵活。但
- C#与C++ dll之间传递字符串string wchar_t* char* IntPtr1、由C#向C++ dll 传入字符串时,参数直接
- 什么是Aop主要介绍springboot中aop的使用,用过Spring框架的都知道,aop是spring框架的两大核心功能之一,还有一个就
- java操作json对象出现StackOverflow错误今天在做项目的时候,遇到一个非常怪异的问题。一个java实体类中存在多个属性,每一
- 之前介绍了SpringBoot集成Jpa的简单使用,接下来介绍一下使用Jpa连接数据库对数据进行排序、分页、条件查询和过滤操作。首先创建Sp
- 在开发应用过程中,客户端与服务端经常需要进行数据传输,涉及到重要隐私信息时,开发者自然会想到对其进行加密,即使传输过程中被“有心人”截取,也
- 背景产品想对多次快速点击做一下优化,想要的效果就是双击不会打开多次但是从开发角度来说,我可以用kotlin的拓展方法来调整这个,但是之前的历
- 本文实例讲述了Java集合定义与用法。分享给大家供大家参考,具体如下:java集合大体可分为三类,分别是Set、List和Map,它们都继承
- SessionFactory在Hibernate中实际上起到了一个缓冲区的作用 他缓冲了HI
- package com.letv.cloud.spider;import java.util.HashSet;import java.uti