1030: [JSOI2007]文本生成器
https://www.lydsy.com/JudgeOnline/problem.php?id=1030
分析：
AC自动机+dp。
正难则反，求满足的，可以求出不满足的，用总的减去。所以考虑如何就出所有的长度为m的串里，没有出现任何一个单词的个数。
建立AC自动机，然后会有一些点是一定不能走的，这些点要么是某些单词的结尾，或者是包含了某些单词（以它结尾的串的后缀是一个单词）。
然后f[i][j]表示当前有多少位，在AC自动机的哪个位置的方案数。枚举下一位是什么，在AC自动机上转移。（注意，可能有许多点有些字符没有边，那么经过了这个字符也是合法的。这些的点贡献也要算上。假设存在这个点，直接转移即可。）
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 #include<set> 8 #include<vector> 9 #include<queue>10 #include<map>11 #define fi(s) freopen(s,"r",stdin);12 #define fo(s) freopen(s,"w",stdout);13 using namespace std;14 typedef long long LL;15 16 inline int read() {17 ????int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;18 ????for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f;19 }20 21 const int N = 105;22 const int C = 200005;23 const int mod = 10007;24 25 char s[N];26 int f[N][C], ch[C][26], val[C], fail[C], q[C], Index, n, m;27 28 void Insert(char *s) {29 ????int u = 0, len = strlen(s + 1);30 ????for (int i=1; i<=len; ++i) {31 ????????int c = s[i] - ‘A‘;32 ????????if (!ch[u][c]) ch[u][c] = ++Index;33 ????????u = ch[u][c];34 ????}35 ????val[u] = 1;36 }37 void build() {38 ????int L = 1, R = 0; fail[0] = 0;39 ????for (int c=0; c<26; ++c) {40 ????????int u = ch[0][c];41 ????????if (u) fail[u] = 0, q[++R] = u;42 ????}43 ????while (L <= R) {44 ????????int u = q[L ++];45 ????????for (int c=0; c<26; ++c) {46 ????????????int v = ch[u][c];47 ????????????if (!v) {48 ????????????????ch[u][c] = ch[fail[u]][c]; continue; // !!!49 ????????????}50 ????????????q[++R] = v;51 ????????????int p = fail[u];52 ????????????while (p && !ch[p][c]) p = fail[p];53 ????????????fail[v] = ch[p][c];54 ????????????val[v] = val[v] ? val[v] : val[fail[v]];55 ????????}56 ????}57 }58 void dp() {59 ????f[0][0] = 1;60 ????for (int i=0; i<m; ++i) {61 ????????for (int j=0; j<=Index; ++j) {62 ????????????if (val[j] || !f[i][j]) continue;63 ????????????for (int c=0; c<26; ++c) { // 不仅要走存在的，也要走不存在的点，存在的点不能走有标记的。 64 ????????????????(f[i + 1][ch[j][c]] += f[i][j]) %= mod;65 ????????????}66 ????????}67 ????}68 }69 int main() {70 ????n = read(), m = read();71 ????for (int i=1; i<=n; ++i) {72 ????????scanf("%s", s + 1);73 ????????Insert(s);74 ????}75 ????build();76 ????dp();77 ????int ans = 1;78 ????for (int i=1; i<=m; ++i) ans = (ans * 26) % mod;79 ????for (int j=0; j<=Index; ++j) 80 ????????if (!val[j]) ans = (ans - f[m][j] + mod) % mod;81 ????cout << ans;82 ????return 0;83 }1030: [JSOI2007]文本生成器
原文地址：https://www.cnblogs.com/mjtcn/p/9726314.html