题意：
一个文本串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 ;
}