KMP算法——(手把手算next数组)

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

KMP算法

  • 该算法核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,从而达到快速匹配的目的。
  • KMP算法与BF算法(暴力算法)区别在于,主串的i不会回退,并且模式串的j不会每次都回到0位置。

第一个问题:为什么主串的i不需要回退?

看如下两个字符串:
a b c d a b g h
a b g
假设此时 i 指向 cj 指向 g,匹配失败。
就算 i 退回到 b 的位置,此时和模式串的 0 位置 a 也不一样。

第二个问题:模式串的j回退的位置?

看如下两个字符串:
a b c a b g h a b c a b c
a b c a b c
假设此时 i 指向 gj 指向 c,匹配失败。
此时 i 不进行回退,因为在这个地方前,两个字符串是有一部分相同的。
因此,我们观察,当我们保持 i 不动, j 退回到第三个位置也就是 c 时,不难发现两个字符串前 a b 是一样的。
因此,我们需要借助 next 数组,帮助我们找到 j 需要回退的位置。


next数组

  • KMP算法的精髓就是next数组,next[j]=k,表示不同的 j 对应一个 k 值;k 表示模式串下标为 j 的元素,匹配失败时,要退回的位置。
  • 求k值的规则:
  • 在模式串中,以下标为 0 开始,以下标为 j-1 结束分别找到两个相同的字符串
    得到的字符串长度就是 k
  • 不管什么数据 next[0]=-1; next[1]=0;

例如求模式串 a b c a b c a b 的next数组(数组下标从0开始)

  • 首先next[0]=-1 next[1]=0
  • 对于数组下标为 j=2c ,寻找以 a 开头,以 b 结尾的两个相同字符串,找不到,则字符串长度为 0, 即 k=0 —— next[2]=0
  • 对于数组下标为 j=3a ,寻找以 a 开头,以 c 结尾的两个相同字符串,找不到,则字符串长度为 0, 即 k=0 —— next[3]=0
  • 对于数组下标为 j=4b ,寻找以 a 开头,以 a 结尾的两个相同字符串,找到 a 字符串,则字符串长度为 1, 即 k=1 —— next[4]=1
  • 对于数组下标为 j=5c ,寻找以 a 开头,以 b 结尾的两个相同字符串,找到 ab 字符串,则字符串长度为 2, 即 k=2 —— next[5]=2
  • 对于数组下标为 j=6a ,寻找以 a 开头,以 c 结尾的两个相同字符串,找到 abc 字符串,则字符串长度为 3, 即 k=3 —— next[6]=3
  • 对于数组下标为 j=7b ,寻找以 a 开头,以 a 结尾的两个相同字符串,找到 abca 字符串,则字符串长度为 4, 即 k=4 —— next[7]=4
  • 因此该字符串的next数组-1 0 0 0 1 2 3 4
  • 在上面next数组计算时,不难发现,我们可以通过前一项的k,计算当前项的k,有两种情况:

情况一:arr[k] == arr[j-1]
例如我们在计算数组a b c a b c a b 中下标为 j=6ak 值时。
此时 j-1=5k=2 指向下标为2的 c,说明存在相同字符串 abarr[0]…arr[k-1=1] == arr[(j-1)-k=3]…arr[(j-1)-1=4]。又此时 arr[k=2] == arr[j-1=5] (== c),那么连接起来便存在相同字符串 abc,即 arr[0]…arr[k=2] == arr[(j-1)-k=3]…arr[j-1=5] 因此在上一项的基础上增加一项(从 ababc),即 next[j] = k+1 = 2+1 = 3
KMP算法——(手把手算next数组)

情况二:arr[k] != arr[j-1]
例如我们在计算数组 a b c a b e a b 中下标为 j=6ak 值时。
此时 j-1=5k=2 指向 c,说明存在相同字符串 abarr[0]…arr[k-1=1] == arr[(j-1)-k=3]…arr[(j-1)-1=4]。又此时 arr[k=2] != arr[j-1=5] ,那么借助 k 下标的 next 值继续回退,回退到了 0 下标,此时 arr[k=0] != arr[j-1=5] 仍然不相等,继续回退 k=-1 ,当 k=-1 数组越界,也就意味着不存在相匹配的字符串,因此 next[j] = k+1 = 0
KMP算法——(手把手算next数组)

总结,如果是情况一或者k=-1数组越界,则 next[j] = k+1。 否则为情况二,则 k=next[k] 一直回退,直到出现情况一或者k=-1数组越界。

  • C代码如下:
void GetNext(char* sub, int* next, int lenSub) {
	next[0] = -1;
	next[1] = 0;
	int j = 2;	// 当前下标
	int k = 0;	// 前一项的k,即前一项回退的下标
	// 此时 j=2 的前一项next数组值为0
	while(j < lenSub) {
		if (k == -1 || sub[j - 1] == sub[k]) {	// 情况一和数组越界情况:next[j] = k+1
			next[j] = k+1;	
			j++;	// 求下一个位置
			k++;
		}
		else {
			k = next[k];	// 情况二:不相等则回退
		}
	}
}

KMP主体

我们得到 next数组 后,便可开始从基础的暴力算法,升级为KMP算法。
借助 next数组,完成 主串 的i不会回退,模式串 的j回退到 next数组 中存放的相应位置。
str 表示主串,sub 表示模式串, pos 表示开始比较的位置。
C代码如下:文章来源地址https://www.toymoban.com/news/detail-417667.html

int KMP(char* str, char* sub, int pos) {
	assert(str && sub);
	int lenStr = strlen(str);
	int lenSub = strlen(sub);
	if (lenStr == 0 || lenSub == 0) {
		return -1;
	}
	if (pos < 0 || pos >= lenStr) {
		return -1;
	}

	// 对模式串sub创建next数组
	int* next = (int*)malloc(sizeof(int) * lenSub);
	assert(next);
	GetNext(sub, next, lenSub);

	// 进行遍历比较
	int i = pos;	// 遍历主串
	int j = 0;	// 遍历子串
	while (i < lenStr && j < lenSub) {
		if (j == -1 || str[i] == sub[j]) {	// j == -1 时,回退越界,一样进行++处理
			i++; j++;
		}
		else {
			j = next[j];	// 根据next数组进行回退
		}
	}

	// 模式串匹配主串,则会在模式串末尾结束
	if (j >= lenSub) {
		return i-j;
	}

	// 模式串不匹配主串
	return -1;
}

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

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

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

相关文章

  • 小白必看、手把手教你利用爬虫爬网页

    接下来从网络爬虫的概念、用处与价值和结构等三个方面,让大家对网络爬虫有一个基本的了解。 网络爬虫及其应用 随着网络的迅速发展,万维网成为大量信息的载体,如何有效地提取并利用这些信息成为一个巨大的挑战,网络爬虫应运而生。网络爬虫(又被称为网页蜘蛛

    2024年02月07日
    浏览(38)
  • 【算法】手把手学会前缀和

    目录 前缀和 前缀和的好处 公式的推导 例题:前缀和 二维前缀和 推导公式  例题: 子矩阵的和 🎵前缀和算法可以理解为是一种 以空间换时间的方式 ,通过建立一个新的数组来 存储从头到当前位置的数据的总和 。 初始化数组  🎵前缀和数组的初始化就是将前  i  个数存

    2024年01月17日
    浏览(42)
  • 【算法】手把手学会二分查找

    目录 简介 基本步骤 第一种二分 第二种二分  例题 搜索插入位置 数的范围 总结  🥥二分查找,又叫折半查找,通过找到数据二段性每次都能将原来的数据筛选掉一半,通过这个算法我们能够将一个一个查找的  O(n)  的时间复杂度优化到  O(logn)  ,极大地提升了查找的效率

    2023年04月08日
    浏览(43)
  • 【算法】手把手学会BFS

    目录 简介 层序遍历 例题 献给阿尔吉侬的花束 全球变暖 🍦宽度优先搜索算法(又称广度优先搜索)是 最简便的图的搜索算法之一 ,之前我们在实现对树的层序遍历时就使用过它。不仅如此它还在求最短路径,找连通块时具有奇效。 🍦层序遍历基本上借助于队列,将队头

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

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

    2024年02月06日
    浏览(48)
  • 手把手教学RRT*(RRTSTAR)三维算法MATLAB仿真(代码可直接运行,视频手把手教学)

            在我以前的作品里有关于RRT算法的视频和代码,今天主要讲解一下RRT*算法的原理。RRT*算法主要是在RRT算法的基础上加上了重写父节点和随机重连的两个步骤。具体的实现方式我想以视频的方式向大家讲解,个人感觉讲解的十分详细。视频连接在这里,希望大家看

    2024年04月17日
    浏览(46)
  • 【STK】手把手教你利用STK进行仿真-STK软件简介01STK基本模型

    STK软件的全称是Satellite Toolkit,即卫星仿真工具包,现在已经改名叫STK,系统仿真工具包,它是由美国AGI(Analytical Graphics现在据说要被别的公司收购)开发,是航天领域最先进的商业化的仿真分析软件。STK于1989年发行至今,经过全世界上万用户的实践检验,已经成为航天领域

    2024年02月19日
    浏览(45)
  • 应用实践|基于Python手把手教你实现雪花算法

    📫 作者简介:「六月暴雪飞梨花」,专注于研究Java,就职于科技型公司后端工程师 🏆 近期荣誉:华为云云享专家、阿里云专家博主、 🔥 三连支持:欢迎 ❤️关注、👍点赞、👉收藏三连,支持一下博主~ 分布式策略ID的主要应用在互联网网站、搜索引擎、社交媒体、在线

    2024年02月21日
    浏览(72)
  • 手把手教你 ,带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法,其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 可以理解为一遍摸扑克牌,一边进行排序 在待排序的元素中,假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(60)
  • 【手把手教学】利用七牛云免费CDN服务为自己网站启用图片CDN加速 - 免费版10G/月

    A) 我的网站原图:       http://assets.xxx.com/ assets/img/banner.jpg B) 七牛CDN图片外链:http://cdn.xxx.com/ assets/img/banner.jpg ( 其中B指向七牛的个人存储空间的同路径文件C,如果C不存在或过期,七牛就会自动向A取图 ) 七牛的CDN与传统的CDN思路一样,例如免费的cloudflare、收费的Amazo

    2024年02月02日
    浏览(129)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包