算法---- KMP算法之我觉得自己说得很好懂 - 简书
算法---- KMP算法之我觉得自己说得很好懂
KMP算法是一种改进的算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为————操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n).
from --百度百科
---首先,我们需要更细致的了解这个算法是为了解决哪种问题.
int main(int argc, const char * argv[])
//观察"hello"字符串与"213helldshello"是否匹配
string dStr = "213helldshehello";
string keyStr = "hello";
for (decltype(dStr.size()) i = 0; i & (dStr.size() - keyStr.size()); ++i) {
//从第一个字符开始匹配,如果不成功就接着匹配第二个字符,以此类推
for (auto j = j & (keyStr.size() + i); ++j) { //开始匹配字符
if (dStr.at(j) != keyStr.at(j)) { //如果不匹配,就终止当前循环
if (j == (keyStr.size() + i - 1)){ //如果最后一个字符也匹配成功,就输出匹配成功
cout && "匹配成功" &&
cerr && "匹配失败";
return -1;
小结:这种最基本的匹配思路是大家能想到的思路上最简单,最直接的方法.只不过我们可以发现他好麻烦呐,每次都要重头匹配.然后就有人琢磨优化,然后我们如今就能得到别人的研究成果--kmp.
kmp算法是一种平移算法(沃渍基取的名字).他把之前匹配的信息保留下来,当此次匹配失败后,下一次不从下一个重新匹配,而是根据前面的匹配信息选择平移一段距离来匹配,具体平移多长的距离,由getNext()方法来决定.所以接下来我们要讨论到底要移动多长合适
观察"hello"字符串与"213helldshello"是否匹配
213helldshello
我们可以发现到这里的时候,只有前4位匹配成功,
根据之前所说的平移,那我们要决定平移多少合适
这么一看,我们完全可以平移4位接着匹配.
但是就会有人开始举反例,比如
ssssshesss
--匹配字符串
这个时候我们同样发现前4个是匹配的,
然后我们发现需要平移多少合适呢?
是不是平移1位就能匹配到啦.
这个就麻烦了,我们完全不知道什么时候移多点,什么时候移少点.这个时候需要引入一个概念
我们观察匹配到的字符串,即如上面的ssssh,他匹配到ssss时发现剩下的h不匹配,此时他的最大匹配串就是ssss.然后我们观察他的首尾有最多几个一样的字符串.
首位的a和末尾的a相同 所以最大公共的就是1
这种字符串找不到首位匹配的,所以为0.
首位的as 相同 所以最大公共的就是2.
这种做法有什么意义呢,当我们发现字符串的长度是n的时候,如果他的公共前后缀(就是前面首位相同的字符串)长度为0,那么我们就平移他的长度n.
asdjsdjassda
开始匹配时,发现前4位是正好匹配的,他的公共匹配是asdj
我们发现他的公共前后缀长度是0,
所以这个时候我们平移4位.
这个时候我们不管怎么去设计后面的数据,都不会发生漏掉匹配串的现象.
比如这两个字符串,如果我们匹配到了4个,而且平移3位就能使其匹配,
那么我们就必须要
asdjsdjassda
我们发现如果要匹配成功,公共匹配的4个最后一位一定要改成a
asdasdjassda
这个时候我们发现他的最大公共前后缀为1,所以就应该平移3位,刚好符合我们的假设.
后面的数字是我设计匹配成功的,
真实案例中,只是可能存在匹配成功,
但是这种平移已经能保证我们不会错过可能成功的案例
自我觉得平移的位数的原理已经讲得非常拎清了!
接下来就开始讲算法,
根据前面的原理,我们肯定是需要一个数组来保存最大匹配成功的公共字符串,然后还需要一个函数来计算这个公共字符串的最大公共前后缀好来决定平移几位.
int main()
目标字符串:asabusakswwlsaksaksawlsdkiis
匹配字符串:saksawl
string deStr("asabusakswwlsaksaksawlsdkiis");
string keyStr("saksawl");
//1.先匹配,找到匹配到的最大字符串,需要一个字符串maxStr来保存
string maxStr("");
//用于循环中计算当前长度
//2.开始匹配
for (int i = 0; i & (deStr.size() - keyStr.size());) {
length = 0;//每次重新搜索都把length置0
steps = 1;//每次平移一段距离都重新计算平移的距离
for (int j = j & (keyStr.size() + i); ++j) {
if (deStr.at(j) != keyStr.at(j-i)) {
if ( length & 1) {
maxStr = keyStr.substr(0,length);
//***************
steps = getNext(maxStr); //这里需要一个函数,来告诉我们每次需要跳过多少次
//***************
//如果当前循环不一致则结束循环
++ //匹配成功字符串长度加1
if (length == keyStr.size()){
cout && "匹配成功" &&
cerr && "匹配不成功";
return -1;
我们可以看到,上面还有一个关键的函数,getNext(maxStr)还没有实现,这个函数告诉我们每次需要平移多少位.我已经用星号标出来啦.
接下来重中之重,俺们怎么实现这个函数getNext(maxStr)
unsigned long getNext(string maxStr){
string::size_type length = maxStr.size();//存放字符串的长度
string str1;
string str2;
int subLen = 0;
for (int i = 1 ; i & ++i) {//截取两段字符串
str1 = maxStr.substr(0,i);
str2 = maxStr.substr(length-i,length);
if(str2 == str1){//比较
return length - subL
这个可能跟网络上的版本有些不同,因为代码都是基于我前面的理解,这些当然可以优化,但我只负责解释清楚kmp算法到底干啥了.
最后,本文如果有些错误请指出,我们共同进步!
一个想讲故事的程序员
引言 人类智力的标志性特征就是它的适应能力，也就是创造和重新整理自己对世界的认识来适应不断变化的目标和环境的能力。这种灵活多变的一个结果就是，全世界涌现出了多种多样的语言。每种语言都提供了一套独特的认知“工具箱”，囊括了一种文化经历数千年发展得到的知识与世界观。每种语言都包...
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt三人同时发现，因此人们称它为Knuth-Morris-Pratt算法（简称KMP）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的...
参考文章 知乎：如何更好的理解和掌握 KMP 算法?从头到尾彻底理解KMPKMP 算法（1）：如何理解 KMP（原创）详解KMP算法字符串匹配——BMH算法 1. 引言 真的是遇事不决问知乎啊，知乎上对于KMP的理解提供了很多文章，July这篇文章比较通俗易懂，需要的可以去...
第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型和基本包装类型 用类型的值（对象）是引用类型的-个实例。在ECMAScript中，引用类型是--种数据结构， 1 I用于将数据和功能组织在一起。它也常被称为类，...
天空因为没有鸟飞过而寂寞 云朵因为没有风吹过而静默 遇 或者 不遇 都 躲不过
文:半夏_FJJY 我是在这样一个百无聊赖的下午想起一个朋友，认识她很多年了，从小学初中到现在，从亲近到疏远。 初中的时候，我们开始了住宿生涯，很巧，我们在一个寝室。所以，我有幸旁观她青春中我觉得最肆意的时光。 记得那时年纪小，没有见识还爱闹。早恋是她青春期里最轰轰...
30岁后，生理功能大约每年减退0.8%。到了中年，机体老化加速。45-55岁，衰老过程加剧，一些重要器官开始老化，生理功能明显减退，体质和精力逐渐衰退。但如能正确调理，可让老化放慢脚步。 假设人的生命颠峰是30岁，器官功能为100%，那么每长一岁，器官功能就有0.8%自然减...
在这里过得好开心啊……那些努力没有白费……曾经的坚持都是对哒^_^
Virtualbox虚拟机Linux server共享文件夹配置 注意：要确保virtualbox的版本足够新，才能成功安装增强功能组件 虚拟机访问宿主机服务 NAT方式连接 找出虚拟路由器IP地址，virtualbox通常是10.0.2.2$ ip route showd...=淡泊以明志，宁静而致远=
。。C++正在学习中。。
如果不愿意让我转载你的东东还请留言给我。
====================
留言簿(15)
随笔分类(51)
随笔档案(54)
积分与排名
阅读排行榜
评论排行榜kmp算法什么意思？_百度知道
kmp算法什么意思？
我有更好的答案
一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。完全掌握KMP算法思想学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。
采纳率：36%
来自团队：
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。　 在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。　 对于next[]数组的定义如下：　1) next[j] = -1
j = 0　2) next[j] = max(k): 0&k&j
P[0...k-1]=P[j-k,j-1]　3) next[j] = 0
其他　如：　P
2　即next[j]=k&0时，表示P[0...k-1]=P[j-k,j-1]　因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]&=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
next（1）不是等于0吗？
很高兴为您解答！kmp算法是一种改进的字符串匹配算法。虽然简短但是希望能帮到您！
为您推荐：
其他类似问题
kmp算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。KMP算法——从入门到懵逼到了解
本博文参考http://blog.csdn.net/v_july_v/article/details/7041827
关于其他字符串匹配算法见http://blog.csdn.net/WINCOL/article/details/4795369
暴力匹配算法
暴力匹配的思路，假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
KMP算法概述
KMP算法用于字符串匹配问题，核心思想是找到子串中的重复出现的连续字符并将其记录到数组中。通过这种方式减少失配后回溯长度，以减少匹配次数。
KMP算法其实是基于暴力匹配，并加上next数组之后的成果。
通俗易懂的解释见：（这是理解后面内容的基础）
KMP算法过程
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，j回溯到next[j]可以发现：KMP算法和暴力匹配算法（BF算法）区别在于KMP算法中i不需要回溯且j回溯到next[j]的位置。
看过上面blog中通俗的解释之后，我们大概理解了KMP算法的核心思想，大概也能写出部分匹配值表。现在我们来搞懂next数组和部分匹配值表的关系。（此处搬来那篇博文中的这个表）
我们所用的移位公式为：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
所以j每次回溯的移动位数就是已经匹配的字符数-对应匹配值，因为对于同一个字符串来
说，每个字符的这些相关信息是固定的，我现在只需要把这个信息放在一个数组里，每次
需要移动时候就直接让j等于对应位置的移动位数信息,这不就轻松加愉快了。由于每次都
通过这个数组j可以移动到它需要去的下一个位置，所以我们不妨将其称为next组，每次执
行的过程就是是j=next[j]
那我们现在就要考虑如何构建next数组。
那么问题就来了，我们移动的位数（即下次j将要去的地方）和当前的字符匹配值并没有什么
卵关系，它只在乎已经匹配了的那个字符相关的信息。既然它不在乎我，那我还管它干嘛，
那么我们所需要的当前移动位数就和当前字符没啥关系了，是时候say
goodbye了。
但是虽然说当前匹配值和当前移动位数已经没什么关系了，它却影响了下一个位置的移动
位数，所以我们要将它和下一个位置关联起来。如此一来，每个当前位置的移动位数都与
前面的匹配值相关，而下一个位置的移动位数又与当前匹配值相关……我们自然而然就明白了
，我只要将table表中的部分匹配值都右移一位，就可以得到next表了。
那么现在给我们一个字符串，我们就可以自己推出它的next数组了。基本工作已经完成了一
半，现在我们的任务就是通过代码的方式写出求next数组的基本方法：
基于之前的理解，我们可以明白next数组是可以通过递推求出的：
1.如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j]
即字符串开始的k-1个和当前位置j之前的k-1个对应相等，那么j下一次回溯的位置就是这个k
（因为前面部分都一致，再进行一遍就是无效回溯了）
2.根据已知的next[0...j]求next[j+1]
1）首先，若p[k]==p[j]，则next[j+1]=next[j]+1=k+1;
这个很好理解，就是只要相同就+1就行了。比如下图中C和C相等，所以next[j+1]=2+1=3;
2）若p[k]!=p[j]，k索引next[k]直到与p[j]相等，此时可用公式next[j+1]=k+1（不能用
next[j+1]=next[j]+1，因为此时k已经变了，所以next[j]已经和k不相等了），若没有，则为0
理解起来就是：如果当前的字符不匹配，那么需要寻找长度更短的前缀后缀，让j回溯到
相应的位置（如下图）
为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？
这又归根到next数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀pj-k
pj-1 pj匹配，
如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[
next[k] ]跟pj还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用p[
next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配，所以不断的递归k
= next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。如下图所示：
现在我们来测试下k回溯是不是可以找到之前相同前后缀：
由于此时的C和D不匹配，所以k走到next[k]即k=0,此时p[0]=p[j]，所以next[j]=k+1=1。即字符E之前的字符串“DABCDABD”中有长度为1的相同前缀和后缀
此时我们终于大概明白了next数组的来历……也能自己敲出代码了，代码如下：
void GetNext(char* p,int next[])
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j & pLen - 1){
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k]){
else k = next[k];
当然，此时的KMP算法还是基础版，还有优化版见：
http://baike.baidu.com/link?url=7TyIFAuf53azP6XofEc5oWivGEp5Gt9Dxnmhy5USg7eyiZzEBWiBVLjle1ZpSBUMU-Zqgeh9qqPiQwRdN4lqEq中的优化部分。
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！我们都有梦想，凭什么不努力
KMP算法总结（纯算法，为优化，没有学应用）
先引入大神通俗易懂的博客内容
KMP 算法，俗称“看毛片”算法，是字符串匹配中的很强大的一个算法，不过，对于初学者来说，要弄懂它确实不易。整个寒假，因为家里没有网，为了理解这个算法，那可是花了九牛二虎之力！不过，现在我基本上对这个算法理解算是比较透彻了！特写此文与大家分享分享！
我个人总结了， KMP 算法之所以难懂，很大一部分原因是很多实现的方法在一些细节的差异。怎么说呢，举我寒假学习的例子吧，我是看了一种方法后，似懂非懂，然后去看另外的方法，就全都乱了！体现在几个方面： next 数组，有的叫做“失配函数”，其实是一个东西； next 数组中，有的是以下标为 0 开始的，有的是以 1 开始的；KMP 主算法中，当发生失配时，取的 next 数组的值也不一样！就这样，各说各的，乱的很！
所以，在阐述我的理解之前，我有必要说明一下，我是用 next 数组的， next 数组是以下标 0 开始的！还有，我不会在一些基础的概念上浪费太多，所以你在看这篇文章时必须要懂得一些基本的概念，例如 “ 朴素字符串匹配 ”“ 前缀 ” ， “ 后缀 ” 等！还有就是，这篇文章的每一个字都是我辛辛苦苦码出来的，图也是我自己画的！如果要转载，请注明出处！好了，开始吧！
假设在我们的匹配过程中出现了这一种情况：
根据 KMP 算法，在该失配位会调用该位的 next 数组的值！在这里有必要来说一下 next 数组的作用！说的太繁琐怕你听不懂，让我用一句话来说明：
返回失配位之前的最长公共前后缀！
什么是最长公共前后缀：
好，不管你懂不懂这句话，我下面的文字和图应该会让你懂这句话的意思以及作用的！
首先，我们取之前已经匹配的部分（即蓝色的那部分！）
我们在上面说到 next 数组的作用时，说到 “ 最长公共前后缀 ” ，体现到图中就是这个样子！
接下来，就是最重要的了！
没错，这个就是 next 数组的作用了 :
返回当前的最长公共前后缀长度，假设为 len 。因为数组是由 0 开始的，所以 next数组让第 len 位与主串匹配就是拿最长前缀之后的第 1 位与失配位重新匹配，避免匹配串从头开始！如下图所示！
（重新匹配刚才的失配位！）
如果都说成这样你都不明白，那么你真的得重新理解什么是 KMP 算法了！
接下来最重要的，也是 KMP 算法的核心所在，就是 next 数组的求解！不过，在这里我找到了一个全新的理解方法！如果你懂的上面我写的的，那么下面的内容你只需稍微思考一下就行了！
跟刚才一样，我用一句话来阐述一下 next 数组的求解方法，其实也就是两个字：
a 、当前面字符的前一个字符的对称程度为 0 的时候，只要将当前字符与子串第一个字符进行比较。这个很好理解啊，前面都是 0 ，说明都不对称了，如果多加了一个字符，要对称的话最多是当前的和第一个对称。比如 agcta 这个里面 t 的是 0 ，那么后面的 a 的对称程度只需要看它是不是等于第一个字符 a 了。
b 、按照这个推理，我们就可以总结一个规律，不仅前面是 0 呀，如果前面一个字符的 next 值是 1 ，那么我们就把当前字符与子串第二个字符进行比较，因为前面的是 1，说明前面的字符已经和第一个相等了，如果这个又与第二个相等了，说明对称程度就是 2 了。有两个字符对称了。比如上面 agctag ，倒数第二个 a 的 next 是 1 ，说明它和第一个 a 对称了，接着我们就把最后一个 g 与第二个 g 比较，又相等，自然对称成都就累加了，就是 2 了。
c 、按照上面的推理，如果一直相等，就一直累加，可以一直推啊，推到这里应该一点难度都没有吧，如果你觉得有难度说明我写的太失败了。
当然不可能会那么顺利让我们一直对称下去，如果遇到下一个不相等了，那么说明不能继承前面的对称性了，这种情况只能说明没有那么多对称了，但是不能说明一点对称性都没有，所以遇到这种情况就要重新来考虑，这个也是难点所在。
如果蓝色的部分相同，则当前 next 数组的值为上一个 next 的值加一，如果不相同，就是我们下面要说的！
如果不相同，用一句话来说，就是：
从前面来找子前后缀
1 、如果要存在对称性，那么对称程度肯定比前面这个的对称程度小，所以要找个更小的对称，这个不用解释了吧，如果大那么就继承前面的对称性了。
2 、要找更小的对称，必然在对称内部还存在子对称，而且这个必须紧接着在子对称之后。
如果看不懂，那么看一下图吧！
好了，我已经把该说的尽可能以最浅显的话和最直接的图展示出来了，如果还是不懂，那我真的没有办法了！
针对KMP算法我在添加一下我自己人为非常重要的认识
1.KMP的核心在于移位代替回溯，我们通过查找出最长的公共前后缀，从而确定了可以最大效率简化我们的时间复杂度的移位的最大长度
先附图在附代码（求next数组的）解释：
void makeNext(const char P[],int next[])
int q,k;//q:模版字符串下标；k:最大前后缀长度
int m = strlen(P);//模版字符串长度
next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
for (q = 1,k = 0; q & ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
while(k & 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k
k = next[k-1];
//不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解
if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
下面我们再来讲解一下利用next数组的KMP算法部分：
先上代码：
#include&stdio.h&
#include&string.h&
void makeNext(const char P[],int next[])
int m = strlen(P);
next[0] = 0;
for (q = 1,k = 0; q & ++q)
while(k & 0 && P[q] != P[k])
k = next[k-1];
if (P[q] == P[k])
int kmp(const char T[],const char P[],int next[])
n = strlen(T);
m = strlen(P);
makeNext(P,next);
for (i = 0,q = 0; i & ++i)
while(q & 0 && P[q] != T[i])
//这里我们采取的是移动模式串的策略，可能看不出来，这需要我们画图来看
q = next[q-1];
if (P[q] == T[i])
if (q == m)
printf("Pattern occurs with shift:%d\n",(i-m+1));
int main()
int next[20]={0};
char T[] = "ababxbababcadfdsss";
char P[] = "abcdabd";
printf("%s\n",T);
printf("%s\n",P );
// makeNext(P,next);
kmp(T,P,next);
for (i = 0; i & strlen(P); ++i)
printf("%d ",next[i]);
printf("\n");
}以上就是我对KMP算法核心的了解
附上自己封装的KMP算法的代码如下：
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#define N 100
template&typename T&
template&typename T& istream& operator&&(istream&,kmp&T&&);
template&typename T& ostream& operator&&(ostream&,kmp&T&&);
template&typename T&
memset(next,0,sizeof(next));
memset(pattern,0,sizeof(pattern));
memset(mother,0,sizeof(mother));
num=plength=mlength=fpos=0;
friend istream& operator&&&&(istream&,kmp&T&&);
friend ostream& operator&&&&(ostream&,kmp&T&&);
void getnextone();
//未优化的
void find();
void count();
T pattern[N];
T mother[N];
int next[N];
//母串中包含的个数
template&typename T&
istream& operator&&(istream& in,kmp&T&& k)
cout&&"请输入母串的长度"&&
cout&&"请输入母串"&&
for(int i=0;i&k.i++) cin&&k.mother[i];
cout&&"请输入模式串的长度"&&
cout&&"请输入模式串"&&
for(int i=0;i&k.i++) cin&&k.pattern[i];
template&typename T&
ostream& operator&&(ostream& out,kmp&T&& k)
cout&&"next数组的内容如下，以供查错"&&
for(int i=0;i&k.i++) cout&&k.next[i]&&' ';
cout&&"母串中包含的传的个数是"&&k.num&&
cout&&"第一次出现模式串的位置是"&&k.fpos&&
template&typename T&
void kmp&T&::getnextone()
//next[0]=0,因为0号位置没有前缀和后缀
//目前最长公共前后缀的长度
//q记录目前扫描的的位置
for(;q&q++)
//永远记住，k代表的是长度，实际上的区间位置是0--k-1适合和额前缀
while(k&0&&pattern[k]!=pattern[q]) k=next[k-1];
//算法中描述的部分
if(pattern[k]==pattern[q]) k++;
//再次匹配，我们扩充最长公共前后缀
next[q]=k;
template&typename T&
void kmp&T&::find()
getnexttwo();
for(;i&i++)
while(j&0&&pattern[j]!=mother[i]) j=next[j-1];
if(pattern[j]==mother[i]) j++;
if(j==plength)
fpos=i-plength+1;
//j-fpos+1=k.plength
cout&&"我们找到了匹配的模式串，第一次出现的位置在"&&fpos&&
cout&&"母串中不存在匹配的模式串"&&
int main()
my.find();
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！