LibreOJ L2576 「TJOI2018」str

链接
难度：\(\texttt{?}\)

有 \(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; 
}