下文 均表示
先考虑一个文件、一个通配字符子串，怎么判断合法的方案数。
定义 表示已经考虑完了字符串中的前 个点，目前将所有*替换之后匹配了目标文件前 个字符的方案数。
转移显然：当 为字母，若文件第 字符与 相等，则
如果 为 *，则
单个时间复杂度 （暴力转移）或 （前缀和优化），总体时间复杂度 至
我们考虑将所有子串的贡献统一处理。
定义 表示已经考虑完了字符串中的前 个点，目前将所有*替换之后匹配了目标文件前 个字符的方案数总和。
那么转移变成：当 为字母，若文件第 字符与 相等，则
如果 为*，则 则 最后，令 （新增一个子串开头）。
最后， 。意为枚举子串右端点。
对于每一个文件求解即可。时间复杂度 。经前缀和优化可做到
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, M = 1000 + 5, P = 998244853;
char c[N], s[M][M];
int len[N];
int n, m;
namespace sub5 {
long long dp[N][M];
void solve() {
long long ans = 0;
for (int k = 1; k <= m; k++) {
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= len[k]; j++) {
if (c[i] == s[k][j] || c[i] == '*')
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % P;
if (c[i] == '*')
dp[i][j] = (dp[i][j] + dp[i][j - 1]) % P;
}
if (c[i] == '*')
for (int j = 0; j <= len[k]; j++) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % P;
dp[i][0]++;
ans = (ans + dp[i][len[k]]) % P;
// cout << ans << " " << k << " " << i << endl;
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= len[k]; j++) dp[i][j] = 0;
}
printf("%lld", ans);
}
} // namespace sub5
int main() {
scanf("%d%d", &n, &m);
scanf("%s", c + 1);
for (int i = 1; i <= m; i++) {
scanf("%s", s[i] + 1);
len[i] = strlen(s[i] + 1);
}
sub5::solve();
return 0;
}
共 1 条回复
对 取模（笑）