先说说kmp模板,本质就是先求小字符串的next数组,即对每个位置i,next[i]以i位置为终点,前缀和后缀相等的最大长度
求出之后以小字符串为基准类似去求大字符串的next,从而根据需要的到数据
参考博客 http://www.cnblogs.com/c-cloud/p/3224788.html
题意就是给你两个字符串,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\n",cas,dp[sl]); } return 0; }
原文:http://www.cnblogs.com/shimu/p/5718939.html