字符串匹配之KMP算法(续)---还原next数组
2023-09-11 14:21:03 时间
相信通过今天的文章,你会对KMP的认识更加深入一层,不止停留在知道怎样计算的层面上了,废话不多说,開始。
通过前面的第一篇文章,知道了怎么求next数组,相信非常多喜欢刨根问底的人就会问,我依照你的做法确实可以解决问题,那么next数组究竟是个神马东西喃?为啥会那样求喃?
next数组为啥那样求?今天翻阅算法导论发现有证明next数组迭代计算的正确性,可以理解点,可是还不到可以写出来的程度,又把july的文章大致浏览下,想看看他是怎么介绍的,发现他把这部分也略过了,在文章最后说用了1年的时间才全然明确理解。看看如今的我,也还是处于尚未全然理解的程度,所以这部分(next数组的计算原因)决定暂且放下不写,释怀一段时间(预计会非常长,由于接下来时间会非常紧)后有精力再学习的时候加上。
所以今天就说说,next数组究竟是个神马东西?
本篇文章以 阮一峰 那篇文章的最后一部分開始,假设你不了解KMP或没看过我的第一篇KMP的文章,那最好先花5到10分钟先阅读也算是预热一下。
一、以"ABCDABD"为例,来了解下前缀,后缀:
- "A"的前缀和后缀都为空集,共同拥有元素的长度为0;- "AB"的前缀为[A],后缀为[B],共同拥有元素的长度为0;- "ABC"的前缀为[A, AB],后缀为[BC, C],共同拥有元素的长度0;- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共同拥有元素的长度为0;- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共同拥有元素为"A",长度为1;- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共同拥有元素为"AB",长度为2;- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共同拥有元素的长度为0。
二、next数组存储的是 模式串中 之前已经匹配的字符 的"前缀"和"后缀"的 最长的 共同拥有元素 的长度。
概念比較绕,注意我上面句子中使用了空格来帮助你理解,以下举个样例说下, 有模式串 T = "ABCDABD"
在求next[j] 时候,我们如果T[0]--T[j-1]都可以匹配成功,这个如果是合理的,由于仅仅有每次匹配失败的时候才会使用next数组来获得下一次匹配開始的位置。
上面的话 请多读几遍。
好,我们来求next[1], 模式串中之前已经匹配的字符是T[0]= A, 在第一部分讲过他的前缀后缀都为空,共同拥有元素长度为 0 ,所以next[1]=0;
求next[4], 模式串中之前已经匹配的字符是T[0]--T[3]={A, B, C, D}, 从第一部分得到他的前缀和后缀共同拥有元素长度为0,所以next[4] = 0;
求next[5], 模式串中之前已经匹配的字符是T[0]--T[4]={A, B, C,D, A}, 从第一部分得到他的前缀和后缀共同拥有元素为'A', 长度为1, 所以next[5]=1;
好了,其它的几个自己试着来推倒推倒。
三、next数组的还有一理解(对于学习后面的BM算法做一点点小小的铺垫)
如果有一例如以下的匹配
留意我图上颜色的两个AB,在D匹配失败的时候,next数组事实上做的就是让前面的AB移动到后面匹配的AB,例如以下图:
这样来避免回溯,加快效率的。在我后面打算要介绍的BM算法中这样的出现的字符串叫做好字符串,哈哈,是不是又长知识了,好了,今天的介绍就到这里为止,这样KMP就算介绍完了。
假设你认为本篇对你有收获,请帮顶。
另外,我本人开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
另外,我本人开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你能够搜索公众号:swalge 或者扫描下方二维码关注我
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/24112823
)
相关文章
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现蓝桥杯VIP算法训练 自行车停放
- Java实现 蓝桥杯 算法提高 数组求和
- Java实现 蓝桥杯VIP 算法提高 统计单词数
- Java实现 蓝桥杯VIP 算法训练 会议中心
- Java实现 蓝桥杯VIP 算法训练 删除多余括号
- Java实现 蓝桥杯VIP 算法训练 最长字符串
- Java实现 蓝桥杯VIP 算法训练 连续正整数的和
- Java实现 蓝桥杯 算法提高 快乐司机
- Java实现 蓝桥杯 算法训练 最大最小公倍数
- Java实现 蓝桥杯 算法训练 动态数组使用
- Java实现 蓝桥杯 算法训练 寻找数组中最大值
- 算法练习之将有序数组转换为二叉搜索树,平衡二叉树
- 重新整理数据结构与算法——稀疏数组[二]
- ML之LoR:逻辑回归LoR算法的简介、应用、经典案例之详细攻略
- Qt中使用openCV修改图片局部颜色算法优化
- 机器学习常识:初学者应该知道的10 大机器学习算法
- 1219. 黄金矿工--dfs算法+回溯法
- 1991. 找到数组的中间位置-贪心算法+前缀和
- 【数据结构与算法】FST 有穷状态转换器详解:Finite State Transducers & 算法核心思想和代码实现(Golang语言)
- 使用OpenCV-Python+Flask+json完美实现网页与本地互相协同数据流传输: NLP模型聊天文本request传输+图像算法结果传输的解决方案
- svd与推荐算法
- 5.5 bisect--数组的二分算法
- 字符串匹配KMP算法
- 01、算法系列,冒泡排序代码实现 + 讲解
- (1)Python-OpenCV视频帧间差分、高斯混合建模、背景差分提取前景目标轮廓、KCF目标跟踪、Meanshift算法跟踪