P3618 误会

题目大意给你两个字符串a和b你可以将a中的与b相同子串替换为*不限制替换次数(可以为0)问你最多可以替换出多少个不同的字符串。解法KMP套dp QWQ。先做一遍KMP再做一次简单dpfor(int i1;in;i){//v为bool数组 if(imv[i-m1]) dp[i](dp[i-m]dp[i-1])%mod; }else{ dp[i]dp[i-1]%mod; } }代码求赞#includebits/stdc.h using namespace std; #define int long long const int N1e55,mod1e97; char a[N],b[N]; bool v[N]; int T,n,m,j,nxt[N],dp[N]; signed main(){ scanf(%lld,T); for(int tt1;ttT;tt){ scanf(%s%s,a1,b1); nstrlen(a1); mstrlen(b1); memset(nxt,0,sizeof nxt); memset(v,0,sizeof v); memset(dp,0,sizeof dp); j0; for(int i2;im;i){ while(jb[j1]!b[i]) jnxt[j]; if(b[j1]b[i]) j; nxt[i]j; } j0; for(int i1;in;i){ while(jb[j1]!a[i]) jnxt[j]; if(b[j1]a[i]) j; if(jm) { v[i-m1]true; } } dp[0]1; for(int i1;in;i){//v为bool数组 if(imv[i-m1]){ dp[i](dp[i-m]dp[i-1])%mod; }else{ dp[i]dp[i-1]%mod; } } printf(Case #%lld: %lld\n,tt,dp[n]); } return 0; }