kmp算法
推荐博客：
（1）http://blog.csdn.net/starstar1992/article/details/54913261
（2）http://www.cnblogs.com/c-cloud/p/3224788.html
前几天学习了kmp算法，今天发现自己理解得还不是很透彻，所以今天就又回头翻了翻大佬们的博客，，，
kmp算法用途：
给你一个主字符串T,和一个目标字符串P,要求你从T中找到P字符串出现的位置或者P字符串出现的次数，正常的思维都是for一遍字符串T,如果从T的 i 下标不能找到P字符串，就返回到 i+1 的位置继续扫描字符串T, 很明显，这个方法的时间复杂度为lenT*lenP ,这只能处理1000*1000以内的数据，因此就需要使用kmp算法。。。。
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 < m; ++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 { k++; } next[q] = k; } }求完next数组，就是要求题目所要求的了，，，
这里给出例题：POJ - 3461
题目就是让你求P字符串在T字符串里面出现的次数，，
求次数代码：
void kmp() { int l=strlen(a);//a字符串就是前面提到的T字符串 int len=strlen(b);//b字符串就是前面提到的T字符串 int i=0,k=0; sum=0; for(i=0,k=0;i<l;i++) { while(k>0&&b[k]!=a[i])//如果b字符串不能在a字符串中走下去， k=next[k-1];//就获取b字符串下一次应该从a字符串出发的起始点 if(b[k]==a[i]) { k++; } if(k==len)//如果发现找到b字符串 { sum++;//就更新次数 } } cout<<sum<<endl; }POJ - 3461题目的全部代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char a[1000000+10],b[10000+10]; int next[10000+10]; int sum; void getnext() { int l=strlen(b); next[0]=0; int i,k; for(i=1,k=0;i<l;i++) { while(k>0&&b[i]!=b[k]) k=next[k-1]; if(b[i]==b[k]) { k++; } next[i]=k; } } void kmp() { int l=strlen(a); int len=strlen(b); int i=0,k=0; sum=0; for(i=0,k=0;i<l;i++) { while(k>0&&b[k]!=a[i]) k=next[k-1]; if(b[k]==a[i]) { k++; } if(k==len) { sum++; } } cout<<sum<<endl; } int main() { int t; cin>>t; while(t--) { scanf("%s%s",b,a); getnext(); kmp(); } return 0; }