[JSOI2007]文本生成器
Analysis
AC自动机+dp
直接从正面做
设(f[i][j][0/1])表示在节点(i)，串长为(j)，是否已经经过结尾点的总方案数，然后从父亲向儿子转移
做(dp)的时候不用跳(fail)，在构建(fail)指针的时候顺带把对于结尾点的标记通过(fail)指针扩展到它在(fail)树上的祖先（不知道这样理解对不对）
ps：大写看成小写调了1h……
放代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 10;
const int mod = 10007;
char s[N];
int n, m, ch[N][30], lst[N], fail[N], val[N], f[N][105][2], sz = 1, ans;
void insert(char *s) {
int u = 0; int n = strlen(s);
for (register int i = 0; i < n; ++i) {
int c = s[i] - 'A';
if (!ch[u][c]) {
memset(ch[sz], 0, sizeof ch[sz]);
val[sz] = 0;
ch[u][c] = sz++;
// cout << u << " " << c << ' ' << ch[u][c] << endl;
} u = ch[u][c];
} val[u] = 1;
}
void getfail() {
queue <int> q;
int u = 0; fail[0] = 0;
for (register int i = 0; i < 26; ++i)
if (ch[0][i]) q.push(ch[0][i]), fail[ch[0][i]] = lst[ch[0][i]] = 0;
while (!q.empty()) {
int r = q.front(); q.pop();
for (register int i = 0; i < 26; ++i) {
u = ch[r][i];
if (!ch[r][i]) {
ch[r][i] = ch[fail[r]][i];
continue;
} q.push(u);
int v = fail[r];
while (v && !ch[v][i]) v = fail[v];
fail[u] = ch[v][i];
val[u] |= val[fail[u]];
lst[u] = val[fail[u]] ? fail[u] : lst[fail[u]];
}
}
}
void dp() {
f[0][0][0] = 1;
for (register int i = 1; i <= m; ++i)
for (register int j = 0; j < sz; ++j)
for (register int k = 0; k < 26; ++k) {
int u = ch[j][k];
// cout << u << ' ' << i << ' ' << j << endl;
if (val[u]) f[u][i][1] = (f[u][i][1] + f[j][i - 1][0] + f[j][i - 1][1]) % mod;
else {
f[u][i][0] = (f[u][i][0] + f[j][i - 1][0]) % mod;
f[u][i][1] = (f[u][i][1] + f[j][i - 1][1]) % mod;
}
}
}
int main() {
cin >> n >> m;
for (register int i = 1; i <= n; ++i) {scanf("%s", s); insert(s);}
getfail();
dp();
for (register int i = 0; i < sz; ++i) ans = (ans + f[i][m][1]) % mod;
cout << ans;
return 0;
}