Codeforces494BObsessiveString题解（KMP+DP）

题目&＃xff1a;CF 494 B.
题目大意&＃xff1a;给定两个字符串$S$和$T$&＃xff0c;在$S$中抽取几个不相交的子串&＃xff0c;使得$T$均是这些子串的子串&＃xff0c;问有多少种方案.
1≤∣S∣,∣T∣≤1051\leq |S|,|T|\leq 10^51≤∣S∣,∣T∣≤105.

仔细一看感觉题目好像比较难&＃xff0c;但看完题解后感觉这也是一道比较容易的套路题&＃xff0c;KMP与DP结合的题做的少啊…

首先很容易想到第一个串的子串必须包含第二个串&＃xff0c;就很自然想到用KMP将第二个串在第一个串中出现的位置都找出来&＃xff0c;那么所有的子串都必须包含这些位置.

考虑计算出一个数组$val[i]$表示第$i$个字符前最近的匹配点&＃xff08;第$i$个点不一定要匹配&＃xff09;&＃xff0c;发现这个数组可以很容易用KMP求出匹配点后稍微处理一下求出.

考虑应用$val$数组&＃xff0c;设$f[i]$表示到前$i$个字符的方案数&＃xff08;所选子串中不一定要包含第$i$个字符&＃xff09;&＃xff0c;然后很容易发现这个状态的转移有两种情况&＃xff1a;
1.去掉第$i$个字符&＃xff0c;也就是$f[i-1]$.
2.找到最近的匹配点$val[i]$&＃xff0c;考虑$f[1..val[i]-1]$&＃xff0c;发现可以只选串$[val[i]..i]$或者在$f[1..val[i]-1]$后面直接加入这个串.

所以转移就是&＃xff1a;
f[i]&＃61;f[i−1]&＃43;val[i]&＃43;∑j&＃61;1val[i]−1f[j]f[i]&＃61;f[i-1]&＃43;val[i]&＃43;\sum_{j&＃61;1}^{val[i]-1}f[j] f[i]&＃61;f[i−1]&＃43;val[i]&＃43;j&＃61;1∑val[i]−1​f[j]

转移出来之后&＃xff0c;发现答案就是$f[n]$了&＃xff0c;所以直接输出就好.

代码如下&＃xff1a;

#includeusing namespace std;#define Abigail inline void
typedef long long LL;const int N&＃61;100000;
const LL mod&＃61;1000000007;char s[N&＃43;9],t[N&＃43;9];
int n,m,nxt[N&＃43;9];
LL f[N&＃43;9],sum[N&＃43;9],val[N&＃43;9];void add(LL &a,LL b){a&＃43;&＃61;b;while (a>&＃61;mod) a-&＃61;mod;}void self_mate(){int j&＃61;0;nxt[1]&＃61;0;for (int i&＃61;2;i<&＃61;m;&＃43;&＃43;i){while (t[i]^t[j&＃43;1]&&j>0) j&＃61;nxt[j];if (t[i]&＃61;&＃61;t[j&＃43;1]) &＃43;&＃43;j;nxt[i]&＃61;j;}
}void mate(){int j&＃61;0;for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){while (s[i]^t[j&＃43;1]&&j>0) j&＃61;nxt[j];if (s[i]&＃61;&＃61;t[j&＃43;1]) &＃43;&＃43;j;if (j&＃61;&＃61;m){val[i]&＃61;i-m&＃43;1;j&＃61;nxt[j];}}
}void solve(){for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)if (val[i]&＃61;&＃61;0) val[i]&＃61;val[i-1];for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){f[i]&＃61;f[i-1];if (val[i]) add(f[i],sum[val[i]-1]&＃43;val[i]);add(sum[i],sum[i-1]&＃43;f[i]);}
}Abigail into(){scanf("%s",s&＃43;1);scanf("%s",t&＃43;1);n&＃61;strlen(s&＃43;1);m&＃61;strlen(t&＃43;1);
}Abigail work(){self_mate();mate();solve();
}Abigail outo(){printf("%I64d\n",f[n]);
}int main(){into();work();outo();return 0;
}