先说说kmp模板，本质就是先求小字符串的next数组，即对每个位置i，next[i]以i位置为终点，前缀和后缀相等的最大长度
求出之后以小字符串为基准类似去求大字符串的next，即把小字符串放到大字符串前面求next数组，当大字符串的某一个位置的next是大于等于小字符串长度时则含有小字符串，这个位置至少要在大字符串内的小字符串长度之后，从而根据需要的到数据
参考博客 http://www.cnblogs.com/c-cloud/p/3224788.html
网上很多模板next数组似乎有问题，比如字符串abacaba，以1为起始位置，c的位置前缀与后缀相同的最长长度是0，网上有一些是2.应该是搞混了next数组求的到底是以位置i为终点的前缀和后缀的最大公共长度，还是求i之前的最大公共长度加1
题意就是给你两个字符串，A,B，A中每一个B字符串都有两种意思，问A总共可以有多少种意思
令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:
末尾不替换含义：dp[i - 1]
末尾替换含义：dp[i - |B|] (A.substr(i - |B| + 1,|B|) = B)
那么对于末尾替换含义的转移，需要快速判断BB能不能和当前位置的后缀匹配，kmp或者hash判断即可。
#include <iostream> #include <map> #include <math.h> #include <algorithm> #include <vector> #include <cstdlib> #include <cstdio> #include <cstring> #include <set> #include<stdio.h> using namespace std; const int N=1e5+10; const int M=1e9+7; char s[N],t[N]; int T,cas,p[N],nt[N],dp[N]; void makeNext()//求next数组，即小字符串中每个位置i，1~i中最长的前缀和后缀相等的长度 { int q,k; int m = strlen(t+1); nt[1] = 0;//下标注意 for (q = 2,k = 0; q <= m; ++q)//q值注意 { while(k > 0 && t[q] != t[k+1])//这里注意因为代码求得的字符串是从一开始所以是k+1，从0开始应为k,相应k变成k-1 //其实就是字符串上移动一位后该与哪位比较，自己仔细看看，但是当k作为长度时是不变的，只有做数组下标时改变 k = nt[k];//下标改变 if (t[q] == t[k+1])//下标改变 { k++; } nt[q] = k; } } void kmp() { int n,m; int i,q; n = strlen(s+1); m = strlen(t+1); makeNext(); for (i = 1,q = 0; i <= n; ++i)//i值 { while(q > 0 && t[q+1] != s[i])//此处为q，一样的意思 q = nt[q];//下标改变 if (t[q+1] == s[i])//下标改变 q++; p[i]=q; if (q == m) q=nt[q];//下标不改变 } } int main() { freopen("in.txt","r",stdin); cin>>T; while(T--) { cas++; scanf("%s%s",s+1,t+1); int sl=strlen(s+1),tl=strlen(t+1); kmp();//kmp模板 dp[0]=1; for(int i=1; i<=sl; i++) if(p[i]>=tl) dp[i]=dp[i-1]+dp[i-tl],dp[i]%=M; else dp[i]=dp[i-1]; printf("Case #%d: %d ",cas,dp[sl]); } return 0; }