知识点:ACAM,DP
原题面:Luogu
简述
给定 \(n\) 个只由大写字母构成的模式串 \(s_1\sim s_n\),给定参数 \(m\)。
求有多少个长度为 \(m\) 的只由大写字母构成的字符串,满足其中至少有一个给定的模式串,答案对 \(10^4 + 7\) 取模。
\(1\le n\le 60\),\(1\le |s_i|,m\le 100\)。
1S,128MB。
分析
?这做法是个套路
先建立 ACAM,建 Trie 图的时候顺便标记所有包含模式串的状态。记这些状态构成集合 \(\mathbf{S}\)。
发现不好处理含有多个模式串的情况,考虑补集转化,答案为所有串的个数 \(26^{m}\) 减去不含模式串的串个数。
考虑 ACAM 上 DP。设 \(f_{i,j}\) 表示长度为 \(i\),在 ACAM 上匹配的结束状态为 \(j\),不含模式串的字符串的个数。
初始化空串 \(f_{0,0} = 1\)。转移时枚举串长,状态,转移函数,避免转移到包含模式串的状态,有:
注意转移时需要枚举空串的状态 0。实现时滚动数组 + 填表即可。
记 Trie 的大小为 \(|T|\),答案即为:
总时间复杂度 \(O(m|T||\sum|)\) 级别。
为什么可以这样转移?
可以发现建立 Trie 图后,这个转移过程就相当于字符串的匹配过程。
可以认为 DP 过程是通过所有长度为 \(i-1\) 的字符串在 ACAM 上做匹配,从而得到长度为 \(i\) 的字符串对应的状态。
代码
//知识点:ACAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 100 + 10;
const int mod = 1e4 + 7;
//=============================================================
int n, m, ans;
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) {
w = (w << 3) + (w << 1) + (ch ^ '0');
}
return f * w;
}
void Chkmax(int &fir_, int sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
namespace ACAM {
int node_num, tr[60 * kN][26], fail[60 * kN], f[2][60 * kN];
bool tag[60 * kN];
void Insert(char *s_) {
int u_ = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[u_][s_[i] - 'A']) tr[u_][s_[i] - 'A'] = ++ node_num;
u_ = tr[u_][s_[i] - 'A'];
}
tag[u_] = true;
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
int v_ = tr[u_][i];
if (v_) {
fail[v_] = tr[fail[u_]][i];
tag[v_] |= tag[fail[v_]];
q.push(v_);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
void Query() {
ans = f[0][0] = 1;
for (int i = 1; i <= m; ++ i) ans = 26ll * ans % mod;
for (int i = 1, now = 1; i <= m; ++ i, now ^= 1) {
memset(f[now], 0, sizeof (f[now])); //caution:reset
for (int j = 0; j <= node_num; ++ j) {
for (int k = 0; k < 26; ++ k) {
if (tag[tr[j][k]]) continue;
f[now][tr[j][k]] += f[now ^ 1][j];
f[now][tr[j][k]] %= mod;
}
}
}
for (int i = 0; i <= node_num; ++ i) {
ans = (ans - f[m % 2][i] + mod) % mod;
}
}
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(s);
}
ACAM::Build();
ACAM::Query();
printf("%d\n", ans);
return 0;
}