<span>HDU5763 Another Meaning（KMP+dp）</span>
题意：
给你一个主串一个子串，然后主串中匹配到子串就可以把当前部分改为*，
问主串有多少中不同的样子
思路：
先KMP预处理主串中所有匹配到子串的末尾位置
然后用dp
dp[N][2]只更新成功匹配的末尾位置
其中dp[i][0]保存当前位置不参与改变*的总情况
dp[i][1]保存当前位置参与改变*的总情况
用一个变量tmp保存这段长度（除了当前位置的l-1长度）中所有的dp[i][1]的和
可以容易的推出dp[i][0]=tmp+dp[i][1]
dp[i][1]=不在当前l长度中的前一个匹配到的位置的dp[0]+dp[1]（最小为1）
附上凌乱的代码。。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <map> #include <queue> #include <vector> using namespace std; typedef long long LL; const int N = 1e5+5; const int M = 1e5+5; const int INF = 0x3f3f3f3f; const LL mod = 1e9+7; int Next[M],l; LL dp[N][2]; char T[N],P[M]; bool yes[N]; void MakeNext(int m) { Next[0]=-1; int i=0,j=-1; while(i<m) { if(j==-1||P[i]==P[j]) { ++i,++j; Next[i]=j; } else j=Next[j]; } } int KMP(int n,int m) { MakeNext(m); int i=0,j=0,ret=0; while(i<n) { if(T[i]==P[j]||j==-1)++i,++j; else j=Next[j]; if(j==m) { ++ret; yes[i]=1; j=Next[j];//可以记录重复的 /*j=0;//不记录重复的*/ } } return ret; } int main() { //freopen("in.txt","r",stdin); int n,m,kase; scanf("%d",&kase); for(int q=1;q<=kase;q++) { l=0; scanf("%s%s",T,P); n=strlen(T),m=strlen(P); memset(dp,0,sizeof(dp)); memset(yes,0,sizeof(yes)); LL cnt=KMP(n,m); LL ans=1; LL tmp=0; int pre=0,ansp=0; for(int i=m;i<=n;i++) { if(yes[i-m]) { tmp-=dp[i-m][1]; while(tmp<0) tmp+=mod; pre=i-m; } if(yes[i]) { ansp=i; dp[i][1]=max(dp[pre][0]+dp[pre][1],1ll)%mod; dp[i][0]=(tmp+dp[i][1])%mod; tmp=(tmp+dp[i][1])%mod; } //printf("%d %d %d %lld %lld\n",i,pre,yes[i],dp[i][0],dp[i][1]); } printf("Case #%d: %I64d\n",q,ansp?(dp[ansp][0]+dp[ansp][1])%mod:1); } return 0; }
查看3道真题和解析
