现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较
此时，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) …………. || (相配) || ≠(失配)匹配串： P(1) ……. p(j-1) p(j)
由此，我们得到关系式 ‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j), ‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) …………. || (相配) || || ?(有待比较)匹配串： P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) …… || (相配) || || || ≠(失配) P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j) || (相配) || || ?(有待比较) P(1) p(2) ……. p(k-1) p(k)
由上，我们得到关系：‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。课本83页不是有个例子吗？就是 图4.6你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！附：KMP算法查找串S中含串P的个数count #include <iostream>#include <stdlib.h>#include <vector>using namespace std;
inline void NEXT(const string& T,vector<int>& next){ //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i<T.size();i++ ){ int j=next[i-1]; while(T[i]!=T[j+1]&& j>=0 ) j=next[j] ; //递推计算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T){ //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector<int> next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index<S.size();++index){ int pos=0; string::size_type iter=index; while(pos<T.size() && iter<S.size()){ if(S[iter]==T[pos]){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next[pos-1]+1; } }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count;}int main(int argc, char *argv[]){ string S="abaabcacabaabcacabaabcacabaabcacabaabcac"; string T="ab"; string::size_type count=COUNT_KMP(S,T); cout<<count<<endl; system("PAUSE"); return 0;}
KMP算法总结 -|浮云 发表于 2005-5-23 17:45:40 假设文本串“t1,t2,…tn”, 模式串为“p1,p2,…pn”,当文本串中的第I个字符与模式中第j个字符不匹配时，文本串的第i个字符再与模式串中的第k个字符进行比较，则模式中前k-1个字符的子串必须满足下面的关系式：’p1,p2…pk-1’=’pj-k+1,pj-k+2…pj-1若令next[j]=k, 则next[j]表明当模式中第j个字符与文本串中相应字符不匹配时，在模式中需要从新和文本串中该字符进行比较的字符的位置。next[j]=0，当j=1时next[j]=max，{k｜1<k<j,且’p1p2…pk-1’=’pj-k+1,pj-k+2…pj-1’}next[j]=1,其他情况此时，kmp算法如下：1）假设以指针i和j 分别指示文本串和模式串中的比较字符，令i和j的初值为1，开始匹配2）若在匹配过程中ti=pj, 则i和j分别增13）若不相等，匹配失败后，则I不变，j退到next[j]位置在进行比较4）若相等，则指针各增1，否则j再退到下一个next值的位置5）依此类推，直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1，继续进行匹配；另一种是j退到值为0（即模式的第一个字符失配），则i和j也分别增1，表明从文本串的狭义个字符起和模式串重新开始匹配。
看它前面是否有一个最长的 "字符串"和从第一个字符开始的 "字符串" 相等， 若一个都没有就为1;如果有，你就把它找出来，看它有多长；next就是其长度加1比如 模式是 "abaabcac" 的 next[j];1.a 一定是 0 //第一个2.b 一定是 13.为a,前一个为b,b != a(a为第一个字符),所以next[a] = 1;4.为a,前一个为a,a == a,相等就再看ab != ba,所以next[a] = 2;(1+1）5.为b,同上理有a==a,相等就再看ab != aa,所以next[b] = 2;(1+1)6.为c,前一个为c, b!=a,ab==ab，所以next[c] = 3;(2+1)7.为a,都没有相等的,所以next[a] = 1;8.为c,a==a,所以next[c] = 2next[j]=01122312
