图解KMP算法,带你彻底吃透KMP

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

模式串匹配——KMP算法

KMP算法一直是一个比较难以理解的算法,本篇文章主要根据《大话数据结构》中关于KMP算法的讲解,结合自己的思考,对于KMP算法进行一个比较详细的解释。

由于博主本人水平有限,难免会出现一些错误。如果发现文章中存在错误敬请批评指正,感谢您的阅读。

字符串模式匹配介绍

相信学习过数据结构与算法的同学一定不会对字符串感到陌生,字符串的逻辑结构与线性表很类似,不同之处是字符串中的元素都是字符。对于字符串这一数据结构,寻找字符串中子串的位置是最重要的操作之一,查找字串位置的操作通常称为串的模式匹配。而KMP算法就是一种字符串模式匹配算法,在介绍KMP算法之前,我们首先了解以下朴素的模式匹配算法是怎样进行的。

朴素的模式匹配算法

假设我们的主串S=“goodgoogle”,子串T=“google”,我们需要在主串中找到子串的位置,比较朴素的想法是用两个指针(指针其实也就是下标i,j)分别指向主串和子串,如果两个指针指向的元素相同则指针后移,不相同则需要回退指针(主串指针回退到上次匹配首位的下一个位置,子串指针回退到开头位置),重复进行上述操作直到主串指针指向主串末尾,即如下所示:

(1) 从主串S的第一位开始,S与T的前三位都匹配成功,第四位匹配失败,此时将主串的指针退回到第二位,子串的指针退回子串开始,即从S[1]开始重新匹配。

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

(2) 主串S从第二位开始于子串T匹配,第一步就匹配失败,将主串指针指向第三位S[2],子串指针指向开头,继续匹配。

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

(3) 同步骤二,第一步就匹配失败,将主串指针移动到第四位S[3],子串指针指向开头,继续匹配。

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

(4) 还是第一步就匹配失败,将主串指针移动到第五位S[4],子串指针指向开头,继续匹配。

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

(5) 到步骤5终于第一步能够匹配上,从S[4]开始指针依次向后移动,六个字母全部匹配上,匹配成功!

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

根据上面的步骤,我们可以得出朴素模式匹配算法的代码如下所示:

int find_sub_string(string s, string t)
{
	int i = 0, j = 0;	//初始化两个指针
    while(i<s.size() && j<t.size()){
        if(s[i] == t[j]){
            i++;	//如果两个指针指向的字符相等
            j++;	//则将两个指针向后移动
        }
        else{
            i = i - j + 1;	//匹配失败,i退回到上次匹配首位的下一位
            j = 0;			//j退回到子串首位
        }
    }
    if(j>=t.size()){	//j走到子串末尾说明匹配成功
        return i - j;	//匹配成功返回主串中子串出现的第一位
    }
    else 
        return -1;		//匹配失败,返回-1
}

既然是朴素(暴力)解法,那必然存在时间复杂度的问题,我们不妨分析以下上述算法的时间复杂度。

最好的情况是一开始就匹配成功了,如主串为"googlegood",子串为"google",此时的时间复杂度为O(m)(m为子串长度)

那么最坏的情况是什么呢?最坏的情况就是每次不成功的匹配都发生在子串末尾,就如《大话数据结构》书中的例子,主串为S=“00000000000000000000000000000000000000000000000001”,子串为T=“0000000001”,推导一下可得此时的时间复杂度度为O((n-m+1)*m)(n为主串长度)。

而在计算机中对字符的存储采用的是ASCII码,字符串可以看成是许许多多个0和l组成,因此这种最坏的情况是很可能出现的,在计算机的运算当中,模式匹配操作可以说是随处可见。这样看来,这个如此频繁使用的算法,朴素做法显得太低效了。

KMP算法

为了避免朴素算法的低效,几位计算机科学家辈D.E.Knuth、J.H.MorTis和V.R.Pratt发表了一个模式匹配算法,可以一定程度上避免重复遍历的问题,该算法就是大名鼎鼎的KMP算法

从暴力匹配到KMP

要理解KMP算法的原理,我们首先需要批判一下朴素算法中有哪些做的不好的地方。

我们将之前的朴素算法的匹配过程合起来看如下面的图所示:

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

我们可以发现,在2、3、4步骤中,主串的首字符与子串的首字符均不等。我们仔细观察可以发现,对于子串"google"来说,首字母"g"与后面的两个字母是不相等的,而在步骤1中主串与子串的前三个字符相等,这就意味着子串的首字符"g"不可能与主串的二、三位相等,故上图中步骤2、3完全是多余的。

也就是说,如果我们知道子串的首字符"g"与后面两个字符不相等(此处需要进行一些预处理,这是后面的重点),我们就不需要再进行2、3步操作,只保留1、4、5步即可。

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

从上面这幅图我们可以惊喜地发现,在使用朴素算法进行匹配时,主串指针需要进行一些回退;而在知道了子串的一些性质后,主串指针不需要再进行回退,只需一直往前走就行,这样就节省了一些时间开销。

你或许还会有疑问,主串指针是不需要回退了,但为啥我的子串指针还要一直回退到开头呢,有没有办法避免这样呢?

当然是有的,我们再举一个例子,假设主串S=“abcababca”,子串T=“abcabx”,那我们采用朴素算法在进行模式匹配的步骤如下所示:

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

由之前一个例子的分析可知由于T串的首字母"a"与之后的字母"b"、"c"不等,故步骤2、3均是可以省略的。

又因为T的首位"a"与T第四位的"a"相等,第二位的"b"与第五位的"b"相等。而在步骤1中,第四位的"a"与第五位的"b"已经与主串s中的相应位置比较过了是相等的。因此可以断定, T的首字符“a”、第二位的字符“b”与S的第四位字符和第五位字符也不需要比较了,肯定也是相等的。所以步骤4、5这两个比较得出字符相等的步骤也可以省略。

所以在这个例子中我们模式匹配的流程为:

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

在这个例子中我们发现,在得知了子串中有相等的前后缀之后,匹配失败时子串指针不需要回退到开头处,而是回退到相等前缀的后一个位置。

补充一下前后缀的概念:前缀指的是不包含尾字符的所有子串;后缀指的是不包含首字符的所有子串

对比两个例子中朴素做法与改进做法的差别,我们可以发现这两种方法的相同点为都是依靠两个指针的移动对比来实现字符串模式匹配,不同之处在于在改进做法中主串的指针i不需要进行回溯,子串的指针j会根据子串中的最长相等前后缀来进行回溯,这样就省去了一些不需要的回溯步骤,从而降低了时间复杂度。

上面就是从暴力模式匹配算法到KMP算法的推导过程,下面我们再介绍KMP算法的具体原理。

KMP算法原理

在学习KMP算法的原理之前,我们需要先学习前缀表这个概念。

顾名思义,前缀表是一张表(或者直接理解为一个数组),表中记录的是字符串中的每个子串的最大相等前后缀的长度,这个概念有点长也有点抽象,我们举一个例子来具体说明一下。

设字符串T=“aabaaf”,我们求一下T的前缀表(用一个数组名为next的数组表示)。

  1. 第一个子串是t0=“a”,易知该子串没有前缀也没有后缀,故next[0]=0
  2. 第二个子串是t1=“aa”,该子串的前缀为"a",后缀也为"a",故next[1]=1
  3. 第三个子串是t2=“aab”,该子串的后缀中一定会有"b",前缀中一定不含有"b",则其没有相等的前后缀,故next[2]=0
  4. 第四个子串是t3=“aaba”,该子串的最大相等前后缀为"a",长度为1,故next[3]=1
  5. 第五个子串是t4=“aabaa”,该子串的最大相等前后缀为"aa",长度为2,故next[4]=2
  6. 第六个子串是t5=“aabaaf”,该子串的后缀中一定会有"f",前缀中一定不含有"f",则其没有相等的前后缀,故next[5]=0

所以我们能得到字符串T的前缀表为:

j 0 1 2 3 4 5
T a a b a a f
next 0 1 0 1 2 0

那既然我们得到了前缀表,前缀表在KMP算法中的作用是什么呢?其实前缀表决定了子串指针j在匹配失败时回溯到的位置

结论:前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。

我们举个例子来说明这个结论,假设主串S=“aabaabaaf”,子串T=“aabaaf”,我们已经求出了子串T的前缀表,采用KMP算法匹配的流程如下:

kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

从上面的流程可以看到,在子串的某一个字符t[j]处匹配失败时,我们需要查找该字符前面的那个子串的最大相等前后缀的长度,即next[j-1],然后使j指针退回到next[j-1],i指针不变,继续匹配,不断重复这个操作知道匹配成功或者j指针大于等于子串长度。在这里j指针之所以退回到next[j-1]的位置我们可以根据例子思考一下,字符"f"前面的子串为"aabaa",该子串的最大相等前后缀为"aa",而该子串的后缀"aa"已经与s[3]s[4]比较过是相等的,那么子串的前缀就一定是与s[3]s[4]相等的,不需要比较,因此我们的j可以从前缀的后面第一个字符开始匹配,而前缀的长度为next[j-1],所以j应该回退到next[j-1]。

在理解了前缀表及其作用之后,KMP算法就可以整体上分为两步:

一、计算前缀表。

二、根据前缀表移动两个指针进行匹配。

下面我们给出KMP算法的代码实现如下:

void get_Next(string s, int next[])		//这个函数对字符串s进行预处理得到next数组
{
	int j = 0;
	next[0] = 0;	//初始化
	for(int i = 1; i<s.size(); i++){	//i指针指向的是后缀末尾,j指针指向的是前缀末尾
		while(j>0&&s[i]!=s[j])	j = next[j-1];	//前后缀不相同,去找j前一位的最长相等前后缀
		if(s[i]==s[j])	j++;	//前后缀相同,j指针后移
		next[i] = j;	//更新next数组
	}
}

上面是计算模式串的前缀表next的代码,其流程见注释。

得到了next数组后,我们进入匹配查找的阶段。

int strSTR(string s, string t)	//这个函数是从s中找到t,如果存在返回t出现的位置,如果不存在返回-1
{
	if(t.size()==0)	return 0;
	get_Next(t, next);
	int j = 0;
	for(int i = 0; i < s.size(); i++){
		while(j>0&&s[i]!= t[j])	j = next[j-1];	
		if(s[i]==t[j])	j++;
		if(j==t.size())	return i - t.size() + 1;
	}
	return -1;
}

下面我们来做一道例题进行巩固。

KMP例题
kmp算法的流程图解,算法与数据结构,算法,数据结构,c++

这是ACwing题库中的831题

用刚刚给出的代码模板可以得出这道题的代码如下:

#include<iostream>
#include<string>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
string s, p;

void get_Next(string s, int ne[])		//这个函数对字符串s进行预处理得到next数组
{
	int j = 0;
	ne[0] = 0;	//初始化
	for (int i = 1; i < s.size(); i++) {	//i指针指向的是后缀末尾,j指针指向的是前缀末尾
		while (j > 0 && s[i] != s[j])	j = ne[j - 1];	//前后缀不相同,去找j前一位的最长相等前后缀
		if (s[i] == s[j])	j++;	//前后缀相同,j指针后移
		ne[i] = j;	//更新next数组
	}
}

int main()
{
	cin >> n >> p >> m >> s;

	get_Next(p, ne);

	for (int i = 0, j = 0; i < m; i++) {	
		while (j > 0 && s[i] != p[j])	j = ne[j - 1];
		if (s[i] == p[j])	j++;
		if (j == n) {
			cout << i - n + 1 << " ";
			j = ne[j - 1];	
		}
	}

	return 0;
}

注意此处不能直接使用之前的strSTR函数,因为模式串在字符串中多次出现,所以需要对strSTR函数进行小小的修改,在匹配完成即j==n之后将j指针指向ne[j-1]

总结

KMP算法主要应用于字符串模式匹配,其核心思想在于使用前缀表从而实现在不匹配时利用之前已经匹配过的信息来减少回溯的过程。理解KMP算法的关键在于理解前缀表的生成,这部分可以手推几次应该就能理解。文章来源地址https://www.toymoban.com/news/detail-719693.html

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

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

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

相关文章

  • KMP算法——通俗易懂讲好KMP算法:实例图解分析+详细代码注解 --》你的所有疑惑在本文都能得到解答

    KMP 是一个 解决模式串在文本串是否出现过 ,如果出现过,最早出现的位置的经典算法。 Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP 算法”,常用于 在一个文本串 S 内查找一个模式串 P 的出现位置 ,这个算法由 Donald Knuth 、 Vaughan Pratt 、 James H. Morris 三人于 1977 年联合发表

    2024年02月07日
    浏览(46)
  • 【数据结构】一篇带你彻底了解栈

    栈:一种线性数据结构,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top), 另一端称为栈底 [Bottom]。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。即最后进入的元素最先被访问。 压栈:栈的插入操作叫做进栈/压栈

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

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

    2024年03月12日
    浏览(63)
  • [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

    ⭐作者介绍:大二本科网络工程专业在读,持续学习Java,努力输出优质文章 ⭐作者主页:@逐梦苍穹 ⭐所属专栏:数据结构。数据结构专栏主要是在讲解原理的基础上拿Java实现 ⭐如果觉得文章写的不错,欢迎点个关注一键三连😉有写的不好的地方也欢迎指正,一同进步😁

    2023年04月17日
    浏览(95)
  • 【数据结构与算法】KMP算法

     在C语言的strstr的实现过程中,所涉及的算法较为简单,或者说只是一个简单的思路而已,在字符串过长时,所涉及的算法复杂度过大,那有没有比较简单的算法呢?这里就涉及到了KMP——由三位大佬提出的,下面我们一起来了解吧!  KMP算法是一种改进的字符串匹配算法

    2024年03月26日
    浏览(48)
  • 数据结构:KMP算法

         KMP算法是由Knuth、Morris和Pratt三位学者发明的,所以取了三位学者名字的首字母,叫作KMP算法。      KMP主要用于字符串匹配的问题,主要思想是 当出现字符串不匹配时,我们可以知道一部分之前已经匹配过的的文本内容,利用这些信息从而避免从头再开始匹配。    

    2024年02月04日
    浏览(42)
  • 数据结构--KMP算法

    模板: 例题:acwing--kmp字符串(831. KMP字符串 - AcWing题库) 给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。 模式串 P 在字符串 S 中多次作为子串出现。 求出模式串 P 在字符串 S 中所有出现的位置的起始下标。 输入格式 第一

    2024年02月11日
    浏览(39)
  • 数据结构KMP算法详解

    目录 1. KMP算法是什么? 2. KMP算法的由来 2.1 需要要解决的问题 2.2 一开始想到的方法 2.3 KMP算法诞生了 3.KMP算法的详解 4.KMP算法的实现 5.KMP算法的改进 KMP算法是一种改进的字符串匹配算法,即可以 快速的从主串中找到子串的算法 ,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人

    2024年02月12日
    浏览(57)
  • 【数据结构】一篇文章带你彻底学会《后缀表达式》

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 🔥c语言系列专栏:c语言之路重点知识整合 🔥 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ 后缀表

    2024年02月05日
    浏览(55)
  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包