题解：P3618 误会

题解：P3618 误会

算法

kmp+dp。

分析

首先，寻找 a 串与 b 串相同的字串，很容易想到 kmp（当然哈希肯定也可以）。我们用一个数组 pos 来表示该位置能否作为子串替代的结尾。接下来，考虑每次遍历到一个可以被替换为 * 的位置终点后会对答案产生怎么样的贡献。设 dp_i 表示遍历到第 i 个位置时有多少种方案。

• 如果这个位置无法被匹配到（即 pos_i\ne 1 ），那么应该直接由 dp_{i-1} 的位置转移过来。 dp_i=dp_{i-1}
• 如果这个位置可以作为被替换的末尾（即 pos_i=1），那么分为两种情况；
  1. 不替换当前子串，那么有 dp_{i-1} 种方案。
  2. 替换当前子串，那么方案数会增加在替换前的位置前一位的方案数（到 i 位置时全部都加上了一种后面接 * 的方案）。 总结一下就是两种相加（改还是不改）： dp_i=dp_{i-1}+dp_{i-lb}

     代码展示

     
     #include<bits/stdc++.h>
     #define endl '\n'
     #define int long long

using namespace std;

const int mod = 1e9+7; const int N = 1e5+10; int T,dp[N],nex[N],pos[N],tot; int cas=0; string a,b;

signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>T; while(T--) { memset(dp,0,sizeof(dp)); memset(pos,0,sizeof(pos)); memset(nex,0,sizeof(nex)); cas++; cin>>a>>b; int la=a.size(); int lb=b.size(); a=' '+a;b=' '+b; int j=0; for(int i=2;i<=lb;i++) { while(j&&b[i]!=b[j+1]) j=nex[j]; if(b[i]==b[j+1]) j++; nex[i]=j; } j=tot=0; for(int i=1;i<=la;i++) { while(j&&a[i]!=b[j+1]) j=nex[j]; if(a[i]==b[j+1]) j++; if(j==lb) { pos[i]=1; j=nex[j]; } } dp[0]=1; for(int i=1;i<=la;i++) { if(!pos[i]) dp[i]=dp[i-1]%mod; else dp[i]=(dp[i-1]+dp[i-lb])%mod; } cout<<"Case #"<<cas<<": "<<dp[la]<<endl; } return 0; }