您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

KMP算法的原理和实现

时间:2020-04-07 17:03:04  来源:  作者:

只要你学过数据结构与算法分析,相信你对KMP算法应该都不陌生吧?如果你没听过,不要紧,今天我们就来聊一聊这个算法。建议最好拿一张草稿纸,然后边看边理解,这样更有助于你对它的理解,更能理解它背后的精髓所在,相信你在理解完该算法之后,一定会大喊一声:妙啊!

KMP算法的诞生

KMP算法是三位大牛:Knuth、Morris和Pratt同时发现的,于是取了他们名字的首字母然后组合起来,就成了该算法的命名。

KMP算法要解决的问题就是查找一个字符串str2是否在另一个字符串str1出现过,也即str1是否包含str2这个子串,举个例子,可以看到下图,str1中包含有str2这个子串(aab)。

KMP算法的原理和实现

 

暴力解

如果想要解决这个问题,我们很容易想到的一个算法是直接暴力遍历解,从左到右一个个匹配。

KMP算法的原理和实现

 

如果这个过程中有某个字符不匹配,之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动,如果不一致,如图,i和j指针指向的字符不相等。

KMP算法的原理和实现

 

str2右移动一位,然后继续以上操作.

KMP算法的原理和实现

 

直到遍历结束,最后匹配成功,可以返回str1包含str2.

KMP算法的原理和实现

 

这种暴力的算法简单粗暴,可以解决该问题,其时间复杂度为O(M*N),M为str1的长度,N为str2的长度。KMP是对暴力解的一个优化,时间复杂度能做到O(M+N),它的核心精髓是利用了以前的比较信息,然后推断此次比较。说起来有点抽象,继续举个例子。

KMP算法

str1和str2刚开始按照从左到右遍历的顺序依次比较,发现到下标为10的时候,b不等于x,那么此时该怎么做?

KMP算法的原理和实现

 

如果按照暴力的方法,是要将str2整个串往右移动一位,然后再次从左到右依次比较。

KMP算法的原理和实现

 

我们想一下,我们有没有必要将str2向右移动一位,然后再从左到右依次比较呢?如果有必要的话,那它的前提条件必定是下图中红色圈起来的两个范围全部匹配上!但是如果我们事先已经知道如果str2右移一位,然后红色圈起来的范围是不可能匹配成功的,我们就不需要让str2右移一位,而让str2右移若干位。这就是KMP的精髓!

KMP算法的原理和实现

 

那么我们到底怎么样才能知道str2到底向右移动几位呢?又是怎么知道str2右移一位是不可能匹配成功的呢?我们还是首先回到第一轮的匹配中。我们已经说了,str2能够右移一位的前提是要下图中绿色两块的字符要全部匹配上,我们才右移动一位,不能再傻傻地无脑向右移动一位了。

KMP算法的原理和实现

 

那么在第一次的比较中,我们发现下标0~9范围内,str1和str2是全部匹配的,换句话说,str2中的绿色两块要完全匹配,我们才右移动!那我们怎么知道str2中的两块绿色是否完全匹配呢?这就又引出了一个KMP中的核心内容——前缀与后缀的最大匹配长度(也就是next数组)。

KMP算法的原理和实现

 

前缀与后缀的最大匹配长度

举个简单的例子,一个字符串abcabck,那么对于k字符来讲,它前面的字符串所构成的前缀与后缀最大匹配长度为3,如下图所示。

KMP算法的原理和实现

 

那么这玩意有什么用呢?回到刚才的例子

KMP算法的原理和实现

 

我们看一下str2相对于下标为10的字符前面的字符串所构成的前缀与后缀最大匹配长度是多少,按照上面的方法算一下,是5。

KMP算法的原理和实现

 

这就意味着,如果像刚才那样右移一位的话,那str2相对于下标为10的前缀与后缀最大匹配长度应该为9,但是现在只有5,所以右移一位肯定不能和str1匹配。

KMP算法的原理和实现

 

那么应该移动多少位呢?没错,就是5位。然后接着去匹配。

KMP算法的原理和实现

 

至此,关于KMP的大体思路已经讲解完毕,接下来的关键就是如何求出一个字符串中对于所有位置的前缀与后缀最大匹配长度。也就是我们常说的next数组。

如何求next数组

我们人为规定了next[0]=-1和next[1]=0,即0位置的前缀与后缀最大匹配长度是-1,而1位置的前缀与后缀最大匹配长度是0.现在我们假设要求i位置的前缀与后缀最大匹配长度,而现在又知道i-1位置的前缀与后缀最大匹配长度为7,那么,如果j位置的字符和i-1位置的字符相等的话,就可以得到i位置的前缀与后缀最大匹配长度为7+1=8.

KMP算法的原理和实现

 

如果i-1位置的字符和j位置的字符不相等的话,而我们又知道j位置的前缀与后缀最大匹配长度为3,那么我们就去看看k位置的字符是否和i-1位置的字符相等,如果相等,则i位置的前缀与后缀最大匹配长度为3+1=4。如果不等,则再继续以上操作,直到跳到0位置处,如果此时0位置还依然和i-1不等的话,那么i位置的前缀与后缀最大匹配长度为0。

KMP算法的原理和实现

 

以上这一段看着可能有点复杂,但是实际上很好理解,大家用纸和笔来画一下就清楚了!

下面是求next数组的代码

 	public static int getIndexOf(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char[] str1 = s.toCharArray();
		char[] str2 = m.toCharArray();
		int i1 = 0;
		int i2 = 0;
		int[] next = getNextArray(str2); // O (M)
		// O(N)
		while (i1 < str1.length && i2 < str2.length) {
			if (str1[i1] == str2[i2]) {
				i1++;
				i2++;
			} else if (next[i2] == -1) { // str2中比对的位置已经无法往前跳了
				i1++;
			} else {
				i2 = next[i2];
			}
		}
		// i1 越界  或者  i2越界了
		return i2 == str2.length ? i1 - i2 : -1;
	}

利用next数组进行字符串匹配行为

按照以上的思路,我们就可以利用next数组去执行KMP算法了,最终我们是要得到str2在str1全匹配的str1的下标位置,以下图为例,最终KMP算法是要返回8,因为str2是在str1的下标为8的位置处匹配上的,如果str2没有被包含在str1中,那么返回-1.

KMP算法的原理和实现

 

下面是利用next数组进行KMP算法的代码

public static int[] getNextArray(char[] ms) {
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;
		int i = 2; // next数组的位置
		int cn = 0;
		while (i < next.length) {
			if (ms[i - 1] == ms[cn]) {
				next[i++] = ++cn;
			} else if (cn > 0) { // 当前跳到cn位置的字符,和i-1位置的字符配不上
				cn = next[cn];
			} else {
				next[i++] = 0;
			}
		}
		return next;
	}


Tags:KMP算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: KMP算法  点击:(36)  评论:(0)  加入收藏
什么是KMPKMP(D.E.Knuth,J.H.Morris,V.R.Prat)是三个发明者的名字首字母命名的。用于字符串匹配的经典算法。常规匹配算法这个算法很抽象,研究了些时间才慢慢弄懂里面的一些...【详细内容】
2020-05-06  Tags: KMP算法  点击:(61)  评论:(0)  加入收藏
只要你学过数据结构与算法分析,相信你对KMP算法应该都不陌生吧?如果你没听过,不要紧,今天我们就来聊一聊这个算法。建议最好拿一张草稿纸,然后边看边理解,这样更有助于你对它的理...【详细内容】
2020-04-07  Tags: KMP算法  点击:(45)  评论:(0)  加入收藏
字符串匹配是计算机的基本任务之一。举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?许多算法可以完成这个任务,(简称KMP)是最常用...【详细内容】
2019-09-29  Tags: KMP算法  点击:(89)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条