链接
难度：\(\texttt{省选/NOI-}\)
有 \(k\) 组，每一组有 \(a_i\) 个字符串 \(t_{k,a_i}\)，询问分别在每一组选一个字符串拼成的字符串在文本串 \(s\) 出现的个数的所有情况的总和对 \(10^9+7\) 取余的值。
数据范围：\(1\le k\le100,1\le a_i\le 10,1\le |t_{i,j}|,1\le |s|\le 10^4\)。
考虑 DP，设 \(f_{i,j}\) 为到第 \(i\) 组匹配到第 \(j\) 位的方案数。
则 \(f_{i,j}\) 只有可能由 \(i-1\) 组，且拼上第 \(i\) 组的其中一个字符串依然能匹配上 \(s\) 对应的位置。
所以可得转移方程 \(f_{i,j}=\sum_{k=1}^{a_i} f_{i-1,j-|t_{i,k}|}(\operatorname{cmp}(tp_{i-1,j-|t_{i,k}|}+t_{i,k},j))\)（\(tp_{i,j}\) 为对于 \(f_{i,j}\) 所拼成的字符串，\(\operatorname{cmp}(t,i)\) 为字符串 \(t\) 是否能在 第 \(i\) 位匹配上 \(s\)）。
匹配 \(s\) 可用 KMP 求解，若匹配成功则说明可以转移。
时间复杂度 \(O(|s|\times\sum a_i)\)。
# include <bits/stdc++.h>
using namespace std;
const int N = 10000;
char S [N + 10], T [N + 10];
int KMP [N + 10];
const int K = 100;
int DP [K + 10] [N + 10];
const int mod = 1000000007;
int main () {
ios :: sync_with_stdio (false);
cin .tie (0);
cout .tie (0);
int k;
cin >> k >> (S + 1);
int n = strlen (S + 1);
for (int i = 0; i <= n - k; ++ i) {
DP [0] [i] = 1;
}
for (int i = 2, j = 0; i <= n; ++ i) {
while (j && (S [i] ^ S [j + 1])) {
j = KMP [j];
}
j += ! (S [i] ^ S [j + 1]);
KMP [i] = j;
}
for (int h = 1; h <= k; ++ h) {
int a;
cin >> a;
while (a --) {
cin >> (T + 1);
int m = strlen (T + 1);
for (int i = 1, j = 0; i <= n; ++ i) {
while (j && (S [i] ^ T [j + 1])) {
j = KMP [j];
}
j += ! (S [i] ^ T [j + 1]);
if (! (j ^ m)) {
j = KMP [j];
DP [h] [i] += DP [h - 1] [i - m], DP [h] [i] %= mod;
}// 匹配成功可以由上一组转移
}
}
}
int ans = 0;
for (int i = k; i <= n; ++ i) {
ans += DP [k] [i], ans %= mod;
}
cout << ans;
return 0;
}