題意：

給你一個主串一個子串，然后主串中匹配到子串就可以把當前部分改為*，

問主串有多少中不同的樣子

思路：

先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; }

?

轉載于:https://www.cnblogs.com/d-e-v-i-l/p/5715698.html

總結

以上是生活随笔為你收集整理的HDU5763 Another Meaning（KMP+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。