以下i表示主串位置,j表示模式串位置,s为主串,t为模式串.
KMP算法的牛逼之处就是免去i的回溯, 否则普通的扫描扫着扫着不相等,i又回溯到之前的起始位置的下一个位置,j也回溯到1,又开始匹配.
而KMP则是i一直向前走,一旦遇到不匹配的字符,j回溯到一个可以用来比较的位置,而j之前的t部分串与s串i之前的部分是最大匹配的,然后检测s[i],t[j]是否相等,相等则i可以+1,j+1,继续检测,此时i能够后移的原因是,i之前的部分串已最长的匹配t串,这种理解只可意会,不可言传....
next的作用: 当扫描过程中,如果s[i]!=t[j],那么j=next[j],然后比较s[i]与t[j],此时.....s[i-1]与......t[j-1]是最长匹配的,如果s[i]==t[j],那么++i,++j,继续扫描下一位,如果不相等,那么继续j=next[j],再找一个次长的匹配,比较s[i]与s[j],如果一直到j==0都没有匹配i位的字符,那么说明整个模式串与s[i]以及之前的一段都没有匹配,则++i,++j, 即继续从j=1,i=i+1比较。
next怎么求的:这个非常飘渺, next只与模式串有关,因为在s与t匹配过程中一旦遇到一个字符不匹配,那么就应该尝试用已经匹配的那一段t与已经匹配的s的部分去匹配,然后比较t的部分匹配的下一个位置与s[i]是否相等. 所以求next就相当于t与t进行匹配的过程, 与KMP算法非常类似的,首先令i=1,j=0,next[1]=0,表示如果t[1]与主串的字符不匹配,那么应该去和t[0]比较且t[0]之前部分匹配,但是t[0]没有字符,所以if j==0, ++i,++j, 这一位t[i]已经没法匹配了。
如果t[i]与t[j],则++i,++j,并且++i,++j之前的i,j之前的段属于匹配的,所以++i,++j以后的next[i]=j,即如果s[某一位]与t[i]不相等,那么就可以根据next[i]找到j,用s[某一位]与t[j]比较看是否相等.
nextval怎么求:这个是next的升级版,思想是建立在next之上的,但是并不是说要先求next才能求nextval, nextval只是在next的思想上进一步优化了。 如果求next的过程中,t[i]==t[j],那么本来可以直接写 next[++i]=++j; 但是这时候有一些问题,如果t[++i]与主串s[某位]不相等的时候,我们用next[++i],结果t[next[++i]]与t[++i]又相等,虽然i之前的t串与s串某一位之前完全匹配,但是这样的比较是没有意义的,因为既然匹配过程中已不相等,根据next滑动t串后的比较位与t之前的比较位一样,肯定也不匹配,所以这时候我们就非常需要nextval发挥作用了。
所以如果求next的过程中,t[++i]==t[++j],那么我们应该让j回溯到nextval[j]以找到一个不相等的位匹配,这样就最终求得了nextval的所有情况.
的确是只可意会不可言传,权当自己的思路笔记了。。。。。。。。。。不指望别人能读懂
分享到:
相关推荐
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
严蔚敏数据结构kmp算法详解PPT学习教案.pptx 本资源摘要信息将对严蔚敏数据结构kmp算法的学习教案进行详细的讲解和分析。KMP算法是字符串匹配算法中的一种重要算法,它可以高效地进行字符串匹配。 首先,我们需要...
本人从严蔚敏 的 数据结构算法一书中 精选的KMP算法 的实例,希望对大家有用!
我们使用的教材是清华大学严蔚敏教授编写的《数据结构(C语言版)》,该教材难度较大,其实验方法特别是ADT方法在教材中介绍较少,KMP算法更是从理论分析的角度介绍了匹配算法和next的计算,自学难度很大。...
严蔚敏-数据结构-kmp算法详解.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
KMP算法讲解,跟严蔚敏的数据结构上的基本一样,还是比较经典。
KMP 算法使用一个称为 失配表(failure function) 的预处理表来提高匹配效率。失配表存储了模式串中每个字符失配后应该跳转到的位置。 在匹配过程中,算法将模式串和文本串逐个字符进行比较。如果字符匹配,则继续...
数据结构(C语言版)严蔚敏版,KMP算法演示示例ppt
严蔚敏版数据结构中的KMP算法的C++语言实现,有结果截图
这些代码主要是针对严蔚敏老师的《数据结构》一书中的大部分伪代码编辑的代码,能够正常运行,是基于C++编写的代码,包括,数组线性表,链表线性表、双向链表、顺序栈、链栈、链队列,顺序队列,循环队列、KMP算法、...
06-003习题课:栈的基本操作、KMP算法回顾 06-004二叉树的定义、性质与存储结构 06-005二叉树的前序、中序和后序遍历的递归与非递归算法 06-006统计二叉树中叶子结点个数、按给定的先序序列建立二叉链表 06-007线索...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
严蔚敏的数据结构中关于KMP算法中Next值求解的C代码
这是基于严蔚敏数据结构中有关KMP算法的NEXT数组的计算过程,与书中的例子基本一致,是学习数据结构字符串KMP算法的一个很要的理解内容。
这本电子书的内容全部由他本人撰写,实现了严蔚敏版数据结构中90%的算法,包括单链表、排序、广义表、kmp算法、迷宫算法、24点算法、回溯法、二叉树,还写了一些小游戏,有贪吃蛇、俄罗斯方块、迷宫、打字游戏、时钟...
《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
严蔚敏数据结构与算法▲课本算法实现
严蔚敏数据结构与算法▲课本算法实现
严蔚敏 〈数据结构〉课程中有关于模式匹配算法的章节。这个程序实现了其中的代码。采用标准C编写。包含普通带带主串回溯的算法和KMP算法
专门针对于此章的大型算法设计题很少,较常见的是根据 KMP 进行算法分析。 5. 多维数组及广义表:基础章节,基于数组的算法题也是常见的,分数比例波动较大,是出题的“可选单元”或“侯补单元”。 6. 树和二叉树:...