KMP算法的及其原理

这篇具有很好参考价值的文章主要介绍了KMP算法的及其原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 KMP算法

首先 我们先了解一下 KMP算法的作用 str1 和str2 字符串 如果str1中包含str2 那么返回头位置

如果不包含返回-1

首先 我们先加入一个概念: 有一个next数组 next[i]的值为 str2 中 以i-1位置为结尾的字符串中 最长相同前缀后缀为多长(相同前缀后缀 不是对称  aba 中相等的后缀为a 而非ab ba(这个是对称) 且不要让前缀\后缀长度等于字符串  因为对于任何一个字符串来说 它本身的最长前缀/后缀都是它本身 肯定相等)

举个例子 a b a b f f位置的next值为2   0 1 位置的next值恒为-1

好 来开下流程 str2先匹配str1 两个指针齐头并进 到达第一个不满足的位置 它位置的next值为5 那么直接从str2的5位置接着匹配下去

KMP算法的及其原理,算法,java,开发语言

 就是从这个X Y为不同的地方 然后str2 Z和str1 Y继续匹配  如果再不相同呢 就找到Z 的next答案 然后从答案位置匹配... 如果一直next到0了 都没匹配成功 那就让str1的指针++ 也就是说从Y+1为开头继续匹配

解释一下原因

KMP算法的及其原理,算法,java,开发语言

 首先我们知道Z和Y匹配 本质上是看以N开头的字符串和整个str2匹配 但是为什么N到Y之间的那段不用看了呢 首先对于str2来说 因为X位置的答案为5 那么str2的前五个(0-4)和后五个一定相等对吧  然后因为我们str1和str2 X Y之前的部分已经判断完相等了对吧  所以str2的0-4 等于 (x-5)~(x-1) 然鸡皮N~Y-1 又和 (x-5)~(x-1)一一对应 所以0-4和N~Y-1 就一定相等

那为什么不能是本质上N+1和0位置上匹配呢 额 因为X Y位置不同了 所以他到这一定会断掉

哎 是不是感觉还有哪不对 是的 这只能解释 N到Y-1的部分不用判断 但是解释不了为什么N之前的不用判断  

好 我们假设N之前有匹配的字符串 

KMP算法的及其原理,算法,java,开发语言

对吧 假设S位置就可以匹配上了 那str2的前八个字符肯定和这个S开始的八个字符相同 再因为Y前的字符和X前的字符一 一相等 所以 S到Y-1 一定和下面str2中X-8到X-1的字符一 一对应 那也可以推出对于str2来说0~7和X-8到X-1相同 那X位置的next值应该是8啊 怎么能是5呢 这就冲突了 对不对 

所以基于这两个原理 str2可以直接和N进行比较

然后看做一个递归过程 如果我Z和Y没匹配上 那是不是又是一个同样的问题 哎 再去找Z的答案 一直找 找到str2开头0位置了 还没找到 那就说明真配不上 这整个一块都不行 你就把Y往下走吧

快速求next数组

反正跳出的时候 cn一定是当前位置的值 那到下一个循环的时候 cn就一定是上一个位置的结果 那str[cn]对应的是什么呢 就是要判断的位置啊 
因为next的值是前缀后缀相同的长度  如果这个位置的值是2  好 那我们就要判断第三个元素相不相同 如果相同 那就是值就是2+1 其实本来应该是前缀长度+1的位置的 但是正好 数组是从0开始的 都省了

那如果这个位置不同呢?  那就说明衔接不上 那我们再往前推一段

假如说a b a s a b a t g  这个数组 它对应位置的值为(是相等 不是对称)

         -1 0 0 1 0 1 2 3 

我们求g g位置本质是求t结尾的前缀后缀相同最大长度 a结尾的最大相同长度为3 哎 如果我这个t正好和第四个位置相同 是不是就直接套上了 可惜不同 那没办法 但是呢 也不一定直接为0 还要看我们3位置的值 因为你不能接在这个后面的话 那更短的位置呢 

假如这种情况 abagababs 我们求s位置的值 也就是以前一个字符结尾的那个值 虽然部门不能接到aba后面让最大相等长度为4 但是我们可以去看更前面 它和ab还是组成了前缀 后缀相同的

画个图直观理解一下

 KMP算法的及其原理,算法,java,开发语言

Y位置的结果 就是以Y-1结尾的最长相等前缀后缀 假如说已经求出来了 这两个方块区间代表 前缀和后缀 我们求Y+1的结果 那就是以Y结尾的最长相等前缀后缀  这两块区间肯定相等的 如果Y和X相等 那是最好的 我们直接上一个位置的值+1 就出结果了 但是不同呢?难道直接归零去比对吗 不 还可以优化

假如说x位置有值 这个值 就代表着前缀a 前缀b是相等的  那么在x的另一侧就有对应的 c 和d 相等

因为根据Y知道 x的左右两个大区间肯定是相等的

所以可以推出a和c相等 b和d相等

有了这几个条件 我们就知道了 a和d相等  所以Y如果和a的下一个字符配上了 那它的结果就等于x结果加1

KMP算法的及其原理,算法,java,开发语言

那一直干到最开始都没匹配上 那就说明 没有了呗

OK我们开始coding文章来源地址https://www.toymoban.com/news/detail-609772.html

 public static int KMP(String str,String match) {
		char [] str1 = str.toCharArray();
		char [] str2 = match.toCharArray();
		int x = 0;
		int y = 0;
		int [] next = getnext(str2);
		while(x<str1.length&&y<str2.length) {
			if(str1[x]==str2[y]) {
				x++;
				y++;
			}else if(next[y]==-1){
				x++
			}else {
				y = next[y];
			}
		}
		return y == str2.length ? x - y : -1;//y走到头了 说明匹配出来了(y要比实际位置+1 走出while循环都这样) x走到头了说明没有
	}
    public static int [] getnext(char [] str) {
		int [] next = new int [str.length];
		next[0] = -1;
		next[1] = 0;
		int index = 2;
		int cn = 0;
		while(index<str.length) {
			if(str[index-1]==str[cn]) {
				next[index++] = ++cn;
			}else if(cn>0) {
				cn = next[cn];
			}else {
				next[index++] = 0;
			}
		}
		return next;
	}

到了这里,关于KMP算法的及其原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 秒懂算法 | KMP算法(Java描述)

    Knuth-Morris-Pratt 算法(简称 KMP)是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。该算法较Brute-Force算法有较大改进,主要是消除了目标串指针的回溯,从而使算法效率有了某种程度的提高。

    2024年02月07日
    浏览(34)
  • KMP算法 Java实现

    Problem: 28. 找出字符串中第一个匹配项的下标 目录 解题方法 思路 构建next数组 回溯查找 复杂度 Code 构建next串 回溯查找next串,最后下标 通过最大前缀后缀能找到下一次未查找到后要回溯的位置 无论如何第一个数的下一次回溯位置肯定是0,因此 next[0]=0 这里的 j 表示前缀起始位

    2024年04月17日
    浏览(31)
  • Java十大经典算法—KMP

    概念 Knuth-Morris-Pratt 字符串查找算法 ,简称为 “KMP 算法”,常用于在一个文本串 S 内查找一个模式串 P 的出现位置,这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表,故取这 3 人的姓氏命名此算法. KMP 方法算法就利用之前判断过信息,通过一个 next 数

    2024年02月02日
    浏览(42)
  • (详细图解)KMP算法(C语言)------可算领悟了这个由三位前辈研究的算法

    目录   前言 一、简介KMP算法 二、朴素的模式匹配算法 第一种朴素的模式匹配算法的写法 第二种朴素的模式匹配算法的写法 一个例子 第三总结 三、KMP算法 1、字符串的前缀、后缀和部分匹配值 2、KMP算法的原理 算法改进 1、主串、子串从数组索引为 1 处开始存储字符 2、主

    2024年03月12日
    浏览(63)
  • C语言数据结构+KMP算法next数组优化计算方法+优化后子串匹配代码实现

    通过我之前那篇KMP算法的讲解,我们可以快速手算KMP算法的next数组,但是之前计算的next数组在一些情况下会有缺陷,比如模式串’aaaab’和主串’aaabaaaab’进行匹配 令模式串指针为j 当第一个元素不匹配时,下一次匹配还是要从模式串的第一个元素与主串匹配,其实我们可以直接写

    2024年02月06日
    浏览(48)
  • 【PID控制原理及其算法】

    本文以自己的学习过程总结而来,将自己的经验写出来以供大家一起学习,如有错误请多指教 PID就是比例、积分、微分,PID算法可以说是在自动控制原理中比较经典的一套算法,在现实生活中应用比较广泛。 常规的模拟 PID 控制系统原理框图如下图所示: 那么使用PID的目的

    2023年04月24日
    浏览(30)
  • SPFA 算法:实现原理及其应用

    SPFA算法,全称为Shortest Path Faster Algorithm,是求解单源最短路径问题的一种常用算法,它可以处理有向图或者无向图,边权可以是正数、负数,但是不能有负环。 1、SPFA算法的基本流程 1. 初始化 首先我们需要起点s到其他顶点的距离初始化为一个很大的值(比如9999999,像是

    2024年02月08日
    浏览(84)
  • Laf 云开发平台及其实现原理

    大家好,我是来自 Laf 团队的王子俊 ,很高兴今天能在这里给大家分享我们 Laf 云开发平台及其实现原理 。本来想说一点什么天气之类的话作为开头,但主持人都说完啦,我就不多说了,还是直接开始今天的分享吧。 在准备 PPT 的时候,我想过很多种的方式来介绍我们是一个

    2024年02月08日
    浏览(40)
  • 多目标粒子群(MOPSO)算法原理及其MATLAB实现

    粒子群算法(PSO)是Eberhart和Kennedy于1995年提出的一种模拟鸟类觅食行为的算法[1],具有操作简单、速度快等特点。但在实际应用中,许多决策问题都是多目标优化问题,采用粒子群算法来处理多目标优化问题是一种有效方法,Coello 等人将粒子群优化算法扩展到多个目标,提出了

    2024年03月11日
    浏览(50)
  • 超详细 | 鲸鱼优化算法原理及其实现(Matlab/Python)

    鲸鱼优化算法(whale optimization algorithm,WOA)是由Mirjalili和Lewis[1]于2016年提出的一种新型群体智能优化搜索方法,它源于对自然界中座头鲸群体狩猎行为的模拟,该算法整个过程包含搜索觅食、收缩包围和螺旋更新位置三个阶段。 鲸鱼优化算法的三个种群更新机制相互独立,因此其

    2024年02月04日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包