KMP算法中nextval的计算方法
KMP算法中nextval的计算方法！
KMP算法即Knuth-Morris-Pratt算法，是模式匹配的一种改进算法，因为是名字中三人同时发现的，所以称为KMP算法。关于nextval数组的求法，可以参考一下思路
int get_nextval(SString T,int &nextval[ ]){
//求模式串T的next函数修正值并存入数组nextval。
i=1; nextval[1]=0; j=0;
while(i
if(j==0||T[i]==T[j]){ ++i;++j;
if (T[i]!=T[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}//get_nextval
根据这段程序来求nextval的值是可以方便计算出来，但如果是应付考研试题或者期末考试就有点麻烦了，下面的思路可以在任何时候帮助大家很方便地求解nextval，希望同学们认真阅读：
首先看看next数组值的求解方法。
next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next
值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。
看起来很令人费解，利用上面的例子具体运算一遍。
1.前两位必定为0和1。
2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。
3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。
4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。
5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。
6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a 进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。
7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。
在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷而产生的，例如主串为“aaabaaaab”、模式串为“aaaab”那么，比较的时候就会发生一些浪费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。
求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种方法是根据next数组值进行推理，两种方法均可使用，视更喜欢哪种方法而定。
使用例子“aaaab”来考查第一种方法。
1.试想，在进行模式匹配的过程中，将模式串“aaaab”与主串进行匹配的时候，如果第一位就没有吻合，即第一位就不是a，那么不用比较了，赶快挪到主串的下一位继续与模式串的第一位进行比较吧，这时，模式串并没有发生偏移，那么，模式串第一位a的nextval值为0。
2.如果在匹配过程中，到第二位才发生不匹配现象，那么主串的第一位必定是a，而第二位必定不为a，既然知道第二位一定不为a，那么主串的第一、二两位就没有再进行比较的必要，直接跳到第三位来与模式串的第一位进行比较吧，同样，模式串也没有发生偏移，第二位的nextval值仍然为0。
3.第三位、第四位类似2的过程，均为0。
4.如果在匹配过程中，直到第五位才发生不匹配现象，那么主串的第一位到第四位必定为a，并且第五位必定不为b，可是第五位仍然有可能等于a。如果万一第五位为a，那么既然前面四位均为a，所以，只要第六位为b，第一个字符串就匹配成功了。所以，现在的情况下，就是看第五位究竟是不是a了。所以发生了下面的比较：
前面的三个a都不需要进行比较，只要确定主串中不等于b的那个位是否为a，即可以进行如下的比较：如果为a，则继续比较主串后面一位是否为b；如果不为a，则此次比较结束，继续将模式串的第一位去与主串的下一位进行比较。由此看来，在模式串的第五位上，进行的比较偏移了4位（不进行偏移，直接比较下一位为0），故第五位b的nextval值为4。
可以利用第一个例子“abaabcac”对这种方法进行验证。
a的nextval值为0，因为如果主串的第一位不是a，那么没有再比较下去的必要，直接比较主串的第二位是否为a。如果比较到主串的第二位才发生错误，则主串第一位肯定为a，第二位肯定不为b，此时不能直接跳到第三位进行比较，因为第二位还可能是a，所以对主串的第二位再进行一次比较，偏移了1位，故模式串第二位的nextval值为1。以此类推，nextval值分别为：01021302。其中第六位的nextval之所以为3，是因为，如果主串比较到第六位才发生不匹配现象，那么主串的前五位必定为“abaab”且第六位必定不是“c”，但第六位如果为“a”的话，那么我们就可以从模式串的第四位继续比较下去。所以，这次比较为：
因为前两位a和b已经确定了，所以不需要再进行比较了。所以模式串第六位的nextval值为这次比较的偏移量3。
。
1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。
3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。
4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval 值为第二位的next值，为1。
5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。
6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。
7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。
KMP 算法我们有写好的函数帮我们计算Next 数组的值和Nextval 数组的值，但是如果是考试，那就只能自己来手算这两个数组了，这里分享一下我的计算方法吧。
计算前缀Next[i] 的值:
我们令next[0] = -1 。从next[1] 开始，每求一个字符的next 值，就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是，这2个"字符串"不能是同一个"字符串")。如果一个都没有，这个字符的next 值就是0；如果有，就看它有多长，这个字符的next 值就是它的长度。
计算修正后的Nextval[i] 值:
我们令nextval[0] = -1。从nextval[1] 开始，如果某位(字符)与它next 值指向的位(字符)相同，则该位的nextval 值就是指向位的nextval 值(nextval[i] = nextval[ next[i] ])；如果不同，则该位的nextval 值就是它自己的next 值(nextvalue[i] = next[i])。
举个例子:
计算前缀Next[i] 的值:
next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。
计算修正后的Nextval[i] 值:
nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0]，nextval[1] = next[1] = 0。nextval[2] = 0;s[2] != s[0]，nextval[2] = next[2] = 0。nextval[3] = -1;s[3] == s[0]，nextval[3] = nextval[0] = -1。nextval[4] = 0;s[4] == s[1]，nextval[4] = nextval[1] = 0。nextval[5] = 0;s[5] == s[2]，nextval[5] = nextval[2] = 0。nextval[6] = -1;s[6] == s[3]，nextval[6] = nextval[3] = -1。nextval[7] = 4;s[7] != s[4]，nextval[7] = next[7] = 4。
模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
文献综述 一般使用的计算机的硬件结构主要反映数值计算的需要，而计算机上的非数值处理的对象基本上是字符串数据，因此在处理字符串数据时比处理整数和浮点数要复杂的很多。随着程序语言将程序的发展，字符串的处理也有了越来越多的研究。子串的定位炒作通常称为串的模式匹配，是各种处理系统中最重要的操作之一。串匹配问题是指从给定的字符序列中找出一个或多个具有某种属性的模式序列，而字符串匹配指的便是从给定的字符序列中找出一个或若干个给定的字符串。字符串匹配算法是一个基础算法，它的解决以及在这个过程中产生的方法对计算机的其他问题都产生了巨大的影响。在我们日常使用计算机的过程中，使用字符串匹配技术的例子十分普遍，例如：入侵检测、病毒检测、信息检索、信息过滤、计算生物学等等都包含了字符串匹配技术。 在字符串匹配技术被广泛应用的同时，众多的科技人员也对其进行了深入的研究，字符串匹配问题现在已经发展成为一门相对独立的科学——字符串学（Stingology）[1][2][3]。字符串匹配技术最先被应用于图书文献目录摘要的查询系统和构建数据的全文检索系统。而后，随着网络安全技术和生物技术的日益发展，在网络安全和生物计算等领域中字符串匹配技术又获得了新的发展空间。 随着网络速度和流量的日益增加，基于网络的入侵检测[4][5]系统面临着严峻的挑战，它的处理、分析速度越来越难以跟上网络流量增加速度，从而极易导致数据包的丢失。解决数据包丢失等问题，提高处理速度是关键。另外对于基于误用的入侵检测系统而言，检测过程中最费时的部分便是入侵特征匹配。 目前，信息资源的高速膨胀已经成为一个全球普遍关注的现象。加利福尼亚大学伯克利分校研究人员发现，仅从1999年至2002年全球新产生的信息量就翻了一番。伴随着信息膨胀，信息的良莠不齐现象也是一个严重困扰人们的问题。大量反动、黄色信息以及国家机密在网络上蔓延和传播，给国建安全和社会稳定造成了严重的威胁，如何对这些不良信息进行网络监控是我们面临的一个重要问题。在信息过滤时，特别是在主干网络上进行过滤与检索，对字符串匹配的实时性要求极高，字符串匹配性能的优劣直接影响了过滤与检索系统的性能。 随着生命科学的发展，人们对生命物质的微观结构也有了越来越清晰的认识。目前，人类基因组序列的绘制工作已完成，Prosite等大型蛋白质重要样本数
实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：
数据结构 实 验 报 告 学院软件学院 年级2009级 班级班 学号 姓名 2010 年 3 月24 日
目录 一、实验内容 (1) 二、实验过程……………………………………….X 三、实验结果……………………………………….X
一、实验内容： 1、实验题目：KMP算法 2、实验要求：实现教材中字串比较kmp算法，比较模式串abaabcac与主串acabaabaabcacaabc。 3、实验目标：了解并掌握串的类型定义和基本操作，并在此基础上实现kmp算法。了解kmp算法的基本原理和next函数的使用。
二、实验过程： 1、任务分配 2、设计思想 （1）KMP算法：在模式匹配中，每当一趟匹配过程出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后，继续进行比较。 （2）next函数：看成一个模式匹配问题，整个模式串既是主串又是模式串，可仿照KMP算法。 3、需求分析 (1) 输入的形式和输入值的范围：输入主串S,模式串T，位置pos (2) 输出的形式：模式串在主串中开始匹配的位置i (3) 程序所能达到的功能：利用kmp算法完成模式串和主串的模式匹 配，并输出模式串在主串中开始匹配的位置 (4) 测试数据： S=acabaabaabcacaabc T=abaabcac Pos=6 4、概要设计 1).抽象数据类型 Class String()定义字符串 Int StrLength()返回串的长度 V oid get_next()求模式串T的next函数值并存入next int kmp()利用模式串T的next函数求出T在主串S中第pos个字符之后的位置的KMP算法 2).算法 a.kmp算法模块：实现主串和模式串的模式匹配 b.next函数模块：实现模式串自身的模式匹配，并存入nxet函数中 c.接收处理命令（初始化数据） 5、详细设计 程序代码（含注释）
对KMP算法的理解 整理者——戴红伟 字符匹配算法的现实意义：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。 （请同时参照课本P53～54相关内容） 1.要理解next[j]=k 中，k的含意； （1）BF算法 假设有字符串 S=S1S2......S N P=P1P2......P M 其中（M （2）KMP算法 为了解决上述的问题，KMP算法被发现。 KMP算法的思想如下。匹配过程中，出现不匹配时，S的指针不进行回朔（原地不动），将P尽可能地向后移动一定的距离，再进行匹配。 如图： （该图引用自互联网） 从上图中我们看到，当S移动到i，P到j的时候失配。这时候i不回朔，而只是将P 向前移动尽可能的距离，继续比较。 假设，P向右移动一定距离后，第k个字符P[k]和S[i]进行比较。 此时如上图，当P[j]和S[i]失配后，i不动，将P前移到K，让P[k]和S[i]继续匹配。现在的关键是K的值是多少？ 通过上图，我们发现，因为黄色部分表示已经匹配了的结果（因为是到了S[i]和P[j]的时候才失配，所以S i-j+1S i-j+2…S i-1 = P1P2…P j-1，见黄色的部分）。所以有： 1、S i-k+1S i-k+2…S i-1 = P j-k+1P j-k+2…P j-1。 所以当P前移到K时，有： 2、S i-k+1S i-k+2…S i-1 = P1P2…P k-1。 通过1，2有 P j-k+1P j-k+2…P j-1 = P1P2…P k-1。 呵呵，此时我们的任务就是求这个k值了。。。 参考：https://www.doczj.com/doc/e26997373.html,/2008-09/122068902261358.html 2.求出k 值 按照课本的求法就可以处理。 课本是已知前j个元素的“前缀函数值”，如何求的j+1个元素的前缀函数值。这里有一个思路要发生转变的地方，把一个模式串分成两个部分，因为我们要找k使得P j-k+1P j-k+2…P j-1= P1P2…P k-1，而这本身就是一个模式匹配问题，所以把模式串的前边部分的子串当作“新的模式串”，这样就很容易理解为什么当t k!=t j时，t1…t next[k]-1 = t j-（next[k]-1）…t j-1了。因为这时候t k匹配失败，需要进一步移动模式子串，所以移动的位置就是next[k]。 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 入 侵 检 测 试 验 实验名称:_ KMP算法实验专业班级: _ 网络工程13-01 学号:_ 姓名: 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 我用自己的语言，试图写一篇比较好懂的KMP算法解释。 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 2. 因为B与A不匹配，搜索词再往后移。 3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符，还是相同。 5. 直到字符串有一个字符，与搜索词对应的字符不相同为止。 6. 这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。 7. 一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 8. 怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。 9. 已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数： 第四章 KMP算法 一实验目的： 熟悉串类型的实现方法，了解KMP算法的实现。 二概要设计： 1.实现KMP匹配算法 int KMPMatch(char *s,char *p) 2.对模式串进行求next操作 void getNext(char *p,int *next) 三详细设计： #include { printf("%c:\n",p[j]); printf("next[%d]=%d\n",j,next[j]); } } int KMPMatch(char *s,char *p) { int next[100]; int i,j; i=0; j=0; getNext(p,next); while(i KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 详解KMP算法中Next数组的求法 例如： 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next值0 1 1 2 2 3 1 2 next数组的求解方法是：第一位的next值为0，第二位的next 值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next 值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。 看起来很令人费解，利用上面的例子具体运算一遍。 1.前两位必定为0和1。 2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。 3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next 值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。 4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。 5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next 值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。 6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。 7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next 值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。 KMP算法小结 Posted on 2011/06/14 by huangchao 主要看了这里，感觉讲的十分的不错，总结一下。 首先声明要搜索的串为S,设长度为n，要匹配的串为M,设长度为m. 先考虑暴力的算法，暴力的算法是遍历S的每一个字符，然后从这个字符开始和M串进行匹配。时间复杂度为O(nm). 怎么在此基础上进行优化？假设现在从某个位置(设为s)开始和M串进行匹配，如果匹配不成功，暴力算法是从这个位置的下一个位置(s+1)进行匹配,直观上来说就是匹配的字符串向后“滑动”了一位。 图1 能不能想办法让M向后移动的距离最大化？考虑最好的情况，如果和M匹配的S中的m个字符和M中的字符没有一个相等，那么能向右移动m位；考虑最坏的情况，比如上图，只能移动一位。 而KMP就是在这里做文章，让M串向后“滑动”的距离最大化。 图2 考虑上面的图，M中灰色部分已经和S的灰色部分匹配上了，而灰色部分后一个字符不匹配，则现在M要向后滑动，假设一直向后滑动，直到如图位置又和S再一次匹配上了，那么从这里我们可以得到如下的结论： ?A段字符串是M的一个前缀。 ?B段字符串是M的一个后缀。 ?A段字符串和B段字符串相等。 这样，如果暂时不考虑S，只看M的话，假设已经匹配的M的字串(即图中M 中灰色部分)为subM，则subM有个【相等】的【前缀】和【后缀】。而且M在遇到不匹配的时候可以直接滑动到使subM的前缀和subM的后缀重合的地方。而M向后滑动的时候，第一次subM的前缀和后缀重合意味着此时这个相等的subM的前缀和后缀的长度是最大的。 我们的任务就是要寻找subM的最长的前缀和后缀相等的串。 知道了这一点，离KMP的真谛也就不远了。现在结合这上面的图模拟一下KMP 算法的整个流程： ?将S串和M串从第一个字符开始匹配； ?如果匹配成功，则subM即灰色部分增加； ?如果不成功，则M向后滑动使滑动后的subM的前缀和滑动前的subM的后缀重合，再进行匹配，如果还不成功，则再次滑动M，直到匹配成功或者M 滑动到X处。如果到了X处，则从M串的起始位置进行匹配。 从上面的步骤可以知道，KMP的关键就是要知道当S串中的字符和M串中的字符不匹配时，S串要和M串中的哪个字符继续进行匹配。这个就是在利用状态机模型来解释KMP算法时的状态转移. KMP是通过一个定义了一个next数组，这个next数组保存了如果S中的字符和M中的字符不匹配时S要和M中的哪个字符重新进行匹配的坐标值。如图2中所示是例子，S中的X位置和M不匹配了，那么S要和M中A段后面的字符进行比较，从图中来看是M向后滑动了。 换句话说，next[i]总是保存了当M[i]不匹配时要从M[next[i]]处进行匹配，这个M[next[i]]可能会匹配，如果还不匹配？那么可能会在M[next[next[i]]]处匹配了。这里同时隐含着一个信息，就是i之前的一段字符和next[i]之前的一段字符是相同的，也就是M[0…i-1]相等的前缀和后缀。 现在考虑next[0],next[1]…next[i]都已经知道了，那么图示如下： #define _CRT_SECURE_NO_DEPRECA TE #include s_i++; p_i++; continue; } else { if (p_i == 0) { s_i++; } else { p_i = next[p_i-1]; //取当前匹配不到之前的字符串的最大相等前缀的最后一个字符 } } for (i = 0; i < s_i - p_i; i++) { putchar(' '); } printf("%s\n",ptr); } return (p_i == plen) ? (s_i - plen) : -1;//返回第一次找到子串的下标位置 } int main() { char str[N] = { 0 }; char ptr[N] = { 0 }; int slen, plen; int next[N]; int ret; printf("请输入主串："); scanf("%s",str); printf("请输入模式串:"); scanf("%s",ptr); slen = strlen(str); plen = strlen(ptr); cal_next(ptr, next, plen); printf("\nnext:"); KMP算法步骤剖析 注：先计算好next值进而推出nextval数值，可在CSND上找到求解方法。 对于上述KMP算法第趟匹配,有一定的难度！接下来，我来分析一下。 先给主串和模式串进行编号： 主串 a b c a a b b a b c a b a a c b a c b a 编号i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 模式串 a b c a b a a 编号j：1 2 3 4 5 6 7 (1)第一趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=5 j=5 时匹配失败 取模式串p第五位的nextval值。nextval=1 故下一趟排序将主串的第i=5位与模式串的第nextval=1位进行比 较。 即得到第二趟排序： (2)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=7 j=3 时匹配失败 取模式串p第三位的nextval值。nextval=1 故下一趟排序将主串的第i=7位与模式串的第nextval=1位进行比 较。 即得到第三趟排序： (3)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=7 j=1 匹配失败 取模式串p第1位的nextval值。nextval=0 当nextval=0时，主串要向后面移动一位 故下一趟排序将主串的第i=7+1=8位与模式串的第1位进行比较。 (4)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=15 j=8 匹配成功！ KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列（其实是）。先看看题吧。 （2011年下半年上午题） （2012年上半年上午题） 其实做这个题很简单，我先说说这个题里的各种概念。 给定的字符串叫做模式串T。j表示next函数的参数，其值是从1到n。而k则表示一种情况下的next函数值。p表示其中的某个字符，下标从1开始。看等式左右对应的字符是否相等。 好了，开始做题了。 首先，要把字符串填入到一个表格中：（拿第一个题为例） 将j导入next函数，即可求得， j=1时，next[0]=0； j=2时，k的取值为(1,j)的开区间，所以整数k是不存在的，那就是第三种情况，next[2]=1； j=3时，k的取值为（1，3）的开区间，k从最大的开始取值，然后带入含p的式子中验证等式是否成立，不成立k取第二大的值。现在是k=2，将k导入p的式子中得，p1=p2，即“a”=“b”，显然不成立， 舍去。k再取值就超出范围了，所以next[3]不属于第二种情况，那就是第三种了，即next[3]=1； j=4时，k的取值为（1，4）的开区间，先取k=3，将k导入p的式子中得，p1p2=p2p3，不成立。再取k=2，得p1=p3，成立。所以next[4]=2； j=5时，k的取值为（1，5）的开区间，先取k=4，将k导入p的式子中得，p1p2p3=p2p3p4，不成立。再取k=2，得p1p2=p3p4，不成立。再取k=2，得p1=p4，成立。所以next[4]=2； j=6时，k的取值为（1，6）的开区间，先取k=5，将k导入p的式子中得，p1p2p3p4=p2p3p4p5，不成立。取k=4，得p1p2p3=p3p4p5，不成立。再取k=3，将k导入p的式子中得，p1p2=p4p5，成立。所以next[4]=3； j=7时，k的取值为（1，7）的开区间，先取k=6，将k导入p的式子中得，p1p2p3p4p5=p2p3p4p5p6，不成立。再取k=5，得 p1p2p3p4=p3p4p5p6 ，不成立。再取k=4，得p1p2p3=p4p5p6 ，成立。所以next[4]=4； KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足,明确next数组需要改进之外。其中,理解算法是核心,会求数组是得分点。不用我多说,这一节内容是本章的重中之重。可能进行的考查方式是:求next和nextval 数组值,根据求得的。 KMP算法即Knuth-Morris-Pratt算法，是模式匹配的一种改进算法，因为是名字中三人同时发现的，所以称为KMP算法。因为偶然接触到有关KMP的问题，所以上网查了一下next数组和nextval数组的求法，却没有找到，只有在CSDN 的资料文件里找到了next数组的简单求法（根据书上提供的程序也可以求到，但一般在课堂讲解的时候，学生难以理解，所以希望以更容易理解的形式来讲解），那位高人说时间关系，先讲到这里，于是讲完了next数组就功成身退了。BS的同时，自己研究了下nextwal数组，发现了其中的简易规律，并写了出来，希望能对需要快速理解KMP中nextval的求法的朋友有所帮助。 int get_nextval(SString T,int &nextval[ ]){ //求模式串T的next函数修正值并存入数组nextval。 i=1; nextval[1]=0; j=0; while(i 改进的模式匹配算法的理论分析 设 T = t0 t1 … t s-1 t s t s+1 t s+2 … t s+j-1 t s+j t s+j+1 … t n-1 P = p0 p1 p2 … p j-1 p m-1． 若在匹配过程中出现了如下情况： t s t s+1t s+2… t s+j-1= p0p1p2… p j-1，(1)但t s+j ≠ p j．也就是说，在匹配过程出现了： T t0 t1 … t s-1t s t s+1t s+2… t s+j-1t s+j t s+j+1… t s+m-1 … t n-1 ‖ ‖ ‖ … ‖ ? P p0p1p2 … p j-1p j p j-1… p m-1 则本次匹配失败． 由朴素的模式匹配算法，我们需要下一趟匹配，即需要验证下式是否成立： t s+1t s+2… t s+j-1 t s+j … t s+m?= p0p1 … p j-2p j-1… p m-1(2)如果（2）式成立，则匹配成功，返回s+1；否则需要再下一趟的匹配：t s+2t s+3… t s+j-1t s+j… t s+m+1?= p0p1… p j-3p j-2 …p m-1 (2')以此类推． 下面给出两个互逆的条件 p0p1… p j-2 = p1p2 …p j-1 (3) p0p1… p j-2 ≠p1p2 …p j-1 (3')显然，这两个条件能且只能满足一个．下面并分情况讨论：【1】如果(3) 式成立，则由(1) (2) (3) 式，可以断定p0 p1 …p j-2 = t s+1 t s+2 … t s+j-1成立，即在（3）式条件下，对(2) 式的验证只需要从p j- 引记 此前一天，一位MS的朋友邀我一起去与他讨论快速排序，红黑树，字典树，B树、后缀树，包括KMP算法，唯独在讲解KMP算法的时候，言语磕磕碰碰，我想，原因有二：1、博客内的东西不常回顾，忘了不少；2、便是我对KMP算法的理解还不够彻底，自不用说讲解自如，运用自如了。所以，特再写本篇文章。由于此前，个人已经写过关于KMP算法的两篇文章，所以，本文名为：KMP算法之总结篇。 本文分为如下六个部分： 1. 第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并两相对照各 自的匹配原理； 2. 第二部分、通过我此前第二篇文章的引用，用图从头到尾详细阐述KMP算法中的 next数组求法，并运用求得的next数组写出KMP算法的源码； 3. 第三部分、KMP算法的两种实现，代码实现一是根据本人关于KMP算法的第二篇文 章所写，代码实现二是根据本人的关于KMP算法的第一篇文章所写； 4. 第四部分、测试，分别对第三部分的两种实现中next数组的求法进行测试，挖掘其 区别之所在； 5. 第五部分、KMP完整准确源码，给出KMP算法的准确的完整源码； 6. 第六步份、一眼看出字符串的next数组各值，通过几个例子，让读者能根据字符串 本身一眼判断出其next数组各值。 力求让此文彻底让读者洞穿此KMP算法，所有原理，来龙去脉，让读者搞个通通透透（注意，本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算，其它部分如第三部分的代码实现二，第五部分，和第六部分的字符串下标i 皆是从1开始的）。 在看本文之前，你心中如若对前缀和后缀这个两个概念有自己的理解，便最好了。有些东西比如此KMP算法需要我们反复思考，反复求解才行。个人写的关于KMP算法的第二篇文章为：六（续）、从KMP算法一步一步谈到BM算法；第一篇为：六、教你初步了解KMP算法、updated（文末链接）。ok，若有任何问题，恳请不吝指正。多谢。 第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 这里有两种KMP算法的详解~大家可以参考 KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一．简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos j=0 起比较S[i+j] 与T[j]，若相等，则在主串S 中存在以i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i 增1，而j 退回至0，重新开始新一轮的匹配。 例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。如图： 当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S 下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：模式匹配KMP算法实验步骤
KMP算法实验
字符串匹配的KMP算法
KMP算法实验报告
(完整word版)KMP算法详解
详解KMP算法中Next数组的求法
经典KMP算法(易理解)
KMP算法源码
KMP算法步骤分析
KMP算法考题
KMP算法演算过程(讲述内容)
KMP算法的理论推导
kmp算法详解
大学课件-KMP算法
相关主题
文本预览