hdu_5763_Another Meaning(dp)

题目链接：hdu_5763_Another Meaning

题意：

一个文本串A，一个模式串B，如果文本串含有模式串B，那么就能组合成多种意思，如下：

In the first case, “ hehehe” can have 3 meaings: “*he”, “he*”, “hehehe”.

In the third case, “hehehehe” can have 5 meaings: “*hehe”, “he*he”, “hehe*”, “**”, “hehehehe”.

题解：

多校的官方题解，我们队当时做也是这样的思路，不过我没用KMP，暴力匹配一样也才15ms,数据比较水

1001 Another Meaning

对于这个问题，显然可以进行DP：

令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:

末尾不替换含义：dp[i - 1]

末尾替换含义：dp[i - |B|] (A.substr(i - |B| + 1,|B|) = B)

那么对于末尾替换含义的转移，需要快速判断BB能不能和当前位置的后缀匹配，kmp或者hash判断即可。

复杂度:O(N)

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+,mod=1e9+;

 char a[N],b[N];

 int dp[N];

 int main(){

     int t,ic=;

     scanf("%d",&t);

     while(t--){

         scanf("%s%s",a+,b+);

         int lena=strlen(a+),lenb=strlen(b+);

         memset(dp,,sizeof(dp)),dp[]=;

         for(int i=;i<=lena;i++){

             dp[i]=(dp[i]+dp[i-])%mod;

             int fg=;

             if(lena-i+>=lenb)for(int j=;j<=lenb;j++){

                 if(a[i+j-]!=b[j])break;

                 if(j==lenb)fg=;

             }

             if(fg)dp[i+lenb-]=(dp[i+lenb-]+dp[i-])%mod;

         }

         printf("Case #%d: %d\n",ic++,dp[lena]);

     }

     return ;

 }

巴特西

hdu_5763_Another Meaning(dp)

1001 Another Meaning

最新文章

热门文章