关键词：
转自
wang0606120221：http://blog.csdn.net/wang0606120221/article/details/7402688
假设KMP算法中的模式串为P，主串为S，那么该算法中的核心是计算出模式串的P的next函数。
KMP算法是在已知的模式串的next函数值的基础上进行匹配的。
由于本次只讨论next的求值过程，因此KMP算法的数学推理过程这里不再讲解。
从KMP算法的数学推理可知，此next函数只取决与模式匹配串自身的特点和主串没有任何关系，此函数
默认认为next[1]=0，由于next[j]=k表示的意义是当模式串和主串的第j个字符不匹配时，那么接下来和主串的第j个
字符匹配的字符是模式串的第k个字符。因此，next[1]=0表示当主串的当前字符和模式串的第1个字符不匹配，接
下来需要用模式串的第0个字符和主串的当前字符匹配，由于模式串下标是从1开始的，所以不可能存在第0个字符，
即接下的匹配动作是主串和模式串同时向右移动一位，继续模式匹配。
例如：主串：a c a b a a b a a b n a c
模式串：a b a a b
主串：a c a b a a b a a b n a c
模式串： a b a a b
主串：a c a b a a b a a b n a c
模式串： a b a a b
此时，主串和模式串不匹配，而next[1]=0，因此，模式串的第0个字符和主串的第2个字符比较，而模式串没有第0个
字符，此时可以把第0个字符理解为空字符，即模式串向右移动一位，主串再继续喝模式串匹配，而此时的主串的当
前字符是第3个字符，整体来看是当主串和模式串的第1个字符不匹配时，主串和模式串同时右移一位，然后继续匹配。
接下来讲解一般情况下的next函数值求解过程。
设next[j]=k，根据KMP算法的模式串的特点可知，‘p1p2......pk-1’=‘pj-k+1......pj-1’，其中k必须满足1<k<j，并且不可能存在k‘>k满足上面等式。那么能够根据next[j]=k计算出next[j+1]的值吗？显然是能够计算出来的，不然我也不废话了，呵呵。
下面讨论具体求解过程：
当知道next[j]=k的值，求next[j+1]的值时候有两种情况，一种是pk=pj，另一种情况是pk!=pj。
1.当pk=pj时，那么可以得出在模式串中存在‘p1......pk’=‘pj-k+1......pj’子串等式。并且不可能存在k‘>k，满足
"p1......pk’ "=" pj-k’+1......pj "等式（该等式中用的是双引号，只是为了区别外边字符串的引号和内部k‘的引号，没有其它意图，特此说明），因为根据KMP算法的说明k是最大的。
因此，显而易见next[j+1]=k+1=next[j]+1。该式表示当主串的当前字符和模式串的第j+1个字符不匹配时，需要使用模式串的第k+1个字符和当前主串字符比较匹配，即主串的当前字符不变，变的只是模式串的字符，可以理解为模式串向右移动j+1-（k+1）=j-k个字符。
2.当pk!=pj时，可知在模式串中不存在‘p1......pk’=‘pj-k+1......pj’等式。表明不能简单的用模式串的第k+1个字符和主串比较，因为pk!=pj，此时需要把模式串向右移动更多的位数，直到找出模式串的前m个字符和主串中的m个字符匹配为止或者没有找到这样的子串，那么意味着模式串需要从第1个字符开始和主串从新匹配。
主串：a c a b a a c a b a a b a a b n a c
模式串： a b a a b
主串：a c a b a a c a b a a b a a b n a c
模式串： a b a a b
在此首先给出了next函数的数值，为了方便说明当pk!=pj时，使用pk=pj的方法是不对的。
next[1]=0，next[2]=1，next[3]=1，next[4]=2，next[5]=2.
此时，i=7，j=5，而s[7]!=t[5]，如果简单按照pk=pj时候的方法，用第k+1=2+1=3个字符和主串的第7个字符比较时，显然不行，因为s[6]=a!=b=t[2]。前面子串都不匹配，那么匹配后面的字符显然是笑话。说明此时模式串需要向右移动更多的位数，知道找到合适的字符或者没有找到，需要从第1个字符重新和主串匹配。
因为已经知道next[j]=k，因此可知模式串中p1=pj-k+1，p2=pj-k+2，......，pk-1=pj-1，则此时应该将模式串继续向右移动直到第m+1个字符，该字符满足’p1......pm‘=’pj-m+1......pj‘，（1<m<k<j）并且不存在m’>m也满足该等式。此时就可以使用第m+1个字符和当前主串字符比较匹配，（假设当前主串的字符索引是i+1）
此时主串中必存在关系式‘si-m+1......si’=‘pj-m+1......pj’=‘p1......pm’，因此用模式串的第m+1个字符和当前主串字符比较匹配是正确的。此时next[j+1]=m+1=next[......next[next[k]]]+1。
这里m=next[......next[next[k]]]，这里解释一下m=next[......next[next[k]]]，由于pk!=pj，因此需要向右移动模式串，
首先移动第next[k]个字符和第j个字符比较，假设next[k]=h，如果ph=pj，
则说明模式串中存在等式‘p1......ph’=‘p-h+1......pj’，（1<h<k<j）（假设主串中当前和模式串比较字符是第i+1个）则主串中必然存在‘si-h+1......si’=‘pj-h+1......pj’=‘p1......ph’等式（1<h<k<j）。也就是说next[j+1]=h+1。
即next[j+1]=next[k]+1。
同理，如果ph!=pj，则模式串还需要继续向右移动，用第next[h]个字符和第j个字符比较，以此类推，直到第j个字符和模式串中的某个字符匹配成功或者不存在u（1<u<j）满足等式‘p1......pu’=‘pj-u+1......pj’。如果找到了匹配字符u，那么
next[j+1]=u+1，否则next[j+1]=1。
下面举例说明该过程：next函数值只与模式串自身的特点有关；
模式串的索引：j 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[1]=0；
计算next[2]：因为p1......p2-1，不可能存在索引k，满足1<k<2，因此next[2]=1；
计算next[3]：因为p3-1=b！=a=p1，next[2]=1，而next[1]=0，所以不存在u，满足上述表达式，next[3]=1；
计算next[4]：next[3]=1，p4-1=a=p1，next[4]=next[3]+1=1+1=2；
计算next[5]：next[4]=2，p2=b，p5-1=a！=p2，pj=p4=a，next[2]=1，p1=a=pj，所以next[5]=next[2]+1=1+1=2；
计算next[6]：next[5]=2，p2=b，p6-1=b=p2，next[6]=next[5]+1=2+1=3；
计算next[7]：next[6]=3，p3=a，p7-1=c！=p3，pj=p6=c，next[3]=1，p1=a！=pj，next[1]=0，因此不存在u，所以，next[7]=1；
计算next[8]：next[7]=1，p1=a，p8-1=a=p1，next[8]=next[7]+1=1+1=2。
为什么当模式串第j个字符和主串不匹配时接着用第next[k]个字符直接和第j个字符比较，而不是用第j-1个字符和主串比较呢？
我的证明过程如下。
证明：因为前提条件是next[j]=k，那么可以得知’p1.......pk-1‘=’p-k+1......pj-1‘，并且k满足1<k<j和不存在h，1<k<h<j，满足上面等式，即‘p1......ph-1’=‘pj-h+1......pj-1’，即此时的k值是最大的。
假设此时主串索引为i+1，模式串为j+1，那么‘p1......pj-1’=‘p2......pj’等式是肯定不能成立的。因为如果该等式成立，那么就会存在等式‘p1......pj-2’=‘p2......pj-1’成立，而根据next[j]=k的前提条件，我们已经得出不存在h，1<k<h，满足等式‘p1......ph-1’=‘pj-h+1......pj-1’，而此时却奇怪得出了存在j-1满足上面等式，和已知条件产生矛盾。
所以，next[k]和j之间的所有字符都是不能满足算法寻找的字符满足的等式的条件的。因此，如果pk!=pj，那么接下来必须用从0到next[k]之间的字符和第j个字符比较匹配，所以本算法首先采用从第next[j]个字符和第j个字符比较匹配。
如果我证明的不对，还请大牛们把正确答案告诉我一下，让我也得到正确的证明过程。谢谢！
终上所述，next的函数表达式如下所示：
0，j=1；
next[j]= MAX{k | ‘p1......pk-1’=‘pj-k+1......pj-1’，1<k<j}，集合不为空；
1，其他情况。
假设next[j]=k。
next[j]+1=k+1，pj=pk；
next[j+1]=1，pk!=pj，不存在字符u，1<u<k，满足等式‘p1......pu’=‘pj-u+1......pj’；
next[......next[next[k]]]+1，pk!=pj，找到了u，1<u<k，‘p1......pu’=‘pj-u+1......pj’。
本博客主要讲的是如何按照地推的思想来计算出所有的next函数， 减少每次都扫描整个模式串计算next数值，通过递归算法可以利用前面已经计算出的next[j]的数值可以计算出next[j+1]，这样可以提高不少效率。
KMP算法的求next数值函数代码如下：其中绿色的行代表代码，其它代表对每一行代码的注释。
void getNext(String p,int[] next)
{
//next初始化next[1]=0，由于需要计算最大k值，因此从第2个字符开始查找匹配子串，使得u满足1<u<j
//’p1......pu-1‘=’pj-u+1......pj-1‘，本算法使用了两个索引指针，i和j，并且初始化i=1，j=0。这里为了计算出next数 //值，主串和模式串都是使用的模式串数据。如
//主串： a b a a b c a c，i=1；
//模式串： a b a a b c a c，j=0.
int i=1; next[1]=0; j=0;
//线性扫描主串，主串不回朔，只能增加，而模式串可能会不断的向右滑动，寻找字符u，使得pu=pj，求解 //next[j+1]。
while(i<=p.length)
{
//由于模式串不存在第0个，因此j==0代表主串和模式串肯定不匹配，此时，主串和模式串都必须增加1个索引，然 //后继续匹配操作。此时j=0+1=1，next[i]=1和当主串和模式串的第0个字符比较得出的结果一致，即此时需要使用模式串的第1个字符和主串匹配比较。另外j==0条件还包含了一种情况是在模式串中找不到字符u，使得pu=pj，此时next[j]都等于1。
//p[i]=p[j]条件表示主串和模式串匹配，因此，主串和模式串都需要增加一个字符索引，假设此时主串索引为i和模式串索引为j，可以得出，’p1......pj‘=’pi-j+1......pi‘，由于i和j都要增加一个字符索引，此时主串为i=i+1，模式串为j=j+1，所以next[i]=j；
if(j==0||p[i]==p[j]) {++i;++j;next[i]=j;}
//当j!=0并且p[i]!=p[j]时，执行下面else代码，该代码表示此时模式串需要向右移动，即为了使下一次while循环比较时候使用第next[j]个字符和主串中的第i个字符匹配比较。
else j=next[j];
}
//当循环结束时候，next数组中存放的就是模式串的next初始化的全部数值。即当当前模式串中的字符和主串中的值不匹配时候，下一步需要使用哪一个字符和主串中的当前字符比较匹配。
}
kmp算法中next数组手工求解
参考技术AKMP算法是一种改进的字符串匹配算法，如果不研究编码的话，手工实现还是比较简单，小型字符串甚至不需要你去求next数组就能看出来怎么移动。但是会有一些题目让你求解next数组，这里就以一个题目讲一下手工求解... 查看详情
数据结构kmp算法中的next函数
kmp算法中next函数具体是怎样实现的，最好能举例分布说明kmp策略：调整子串T的位置j，使得S[i-j+1,......i]与T[1,2,....j]保持匹配且新的S[i+1]与T[j+1]恰好匹配,否则j回移或移动i(使得S[i]=T[1]).直至j=T.length.匹配完成.kmp算法的的流程大致... 查看详情
kmp算法(代码片段)
目录简述暴力算法与整体框架暴力KMP框架next数组最长前缀后缀引理根据引理求解next数组f数组求解求解模板题总结简述KMP算法，又称模式匹配算法，能够在线性时间内判定字符串(A[1-N])是否为字符串(B[1-M])的子串。对于刚刚接触KM... 查看详情
kmp的next数组求法详解
近几天学习kmp算法，在next数组求解上受苦颇深，看了不少博客，感觉写得都不够清晰，所以想按照自己理解的过程来尝试写一下，也便于以后温习。关于kmp算法的介绍，网上博文有很多，就不再赘述&#x... 查看详情
kmp算法求next数组
next数组的求解方法是：第一位的next值为0，第二位的next值为1。后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向... 查看详情
kmp算法模式匹配——手工求解next和nextval数组值
本文需要了解KMP算法基本流程和相关概念，如有问题，请先进行基础学习：链接:天勤-KMP算法易懂版求解next数组值给定模式串：“ababaaab”，求解其next数组值。例子里面的ababaaab，我们定义一个i为模式串的... 查看详情
经典算法——kmp，深入讲解next数组的求解(代码片段)
前言 之前对kmp算法虽然了解它的原理，即求出P0···Pi的最大相同前后缀长度k；但是问题在于如何求出这个最大前后缀长度呢？我觉得网上很多帖子都说的不是很清楚，总感觉没有把那层纸戳破，后来... 查看详情
kmp算法模板及理解
kmp算法是复杂度为O(n+m)的字符串匹配算法;首先kmp算法的核心是在模式串中获得next数组,这个数组表示模式串的子串的前缀和后缀相同的最长长度;这样在匹配的过程中如果指到不匹配的位置,模式串用next数组进行跳转到符合的位置... 查看详情
kmp算法实践与简单分析
一、理解next数组1、约定next[0]=-1,同时可以假想在sub串的最前面有一个通配符“*”，能够任意匹配。对应实际的代码t<0时的处理情况。2、next[j]可以有如下的几种理解思路：1）next[j]为sub[j]前面的字符串的前后缀字符串匹配的最... 查看详情
kmp算法
串′ababaaababaa′的next数组为：011234223456先从人的分析角度去分析怎么做。。。。next数组下标从1开始计算next[1]肯定是0next[2]肯定是1next[n]的情况，将前面n-1个字符，计算从首尾开始组成最大的相同子串的长度，如... 查看详情
数据结构与算法——字符串匹配问题(kmp算法)
参考技术AKMP算法也是比较著名的模式匹配算法。是由D.E.Knuth,J.H.Morrs和VR.Pratt发表的一个模式匹配算法。可以大大避免重复遍历的情况。如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母"f"和"x"不相等。如下图：T=... 查看详情
kmp算法的next[]数组通俗解释
...中查找一个子字符串有很多方法。KMP是一种最常见的改进算法，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。当然我们可以看到这个算法针对的是子串有对称属性，如果有对称属性，那么就需... 查看详情
改进的kmp算法的执行过程
比如有模式串 t="aaaabaac" 首先我们至少光看的话，发现未修正的next数组是很好列出来的是next:0,1,2,3,4,1,2,3在这个基础上我们可以很容易的写出修正好的nextVal数组：设nextVal[1]=0;(1)i=2,看next[i]=next[2]=1=j,因为t[i]==t[j]即t[2]==t[1],... 查看详情
数据结构串---kmp模式匹配算法之获取next数组(代码片段)
（一）获取模式串T的next数组值1.回顾我们所知道的KMP算法next数组的作用next[j]表示当前模式串T的j下标对目标串S的i值失配时，我们应该使用模式串的下标为next[j]接着去和目标串失配的i值进行匹配而KMP算法的next求值函数我们可... 查看详情
kmp算法
废话不多说，看毛片算法的核心在于next数组。很多地方用的都是严书上的方法来求解next数组，代码确实简洁明了，但是可能对于初学者来说不容易想到，甚至不是一下子能理解。(好了，其实我说的就是自己，别笑)以下为严师... 查看详情
kmp算法(代码片段)
目录KMP算法基本思想计算next数组前缀和后缀公共部分的最大长度next数组匹配字符串KMP算法基本思想算法由两部分组成计算ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的next数组匹配ptr和str，当ptr失配时，利用nex... 查看详情
从头到尾彻底理解kmp
...不够，故才迟迟没有修改本文。 然近期因开了个算法班，班上专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发... 查看详情
kmp算法
KMP算法KMP算法的简介 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，简称KMP算法。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现... 查看详情