【AC自动机】文本生成器

【题目链接】

https://loj.ac/problem/10063

 

【题意】

给出长度为m，n个模式串，请问只要长度为m的串中有一个模式串就算是可读。

 

【分析】

其实如果直接分析全部可读的情况，一个串，两个串，……n个串可读。

明显是很复杂而且是做不出来的。

正难则反，其实我们可以需要通过一个（所有可能-全部不可读的情况）不就是答案的方案吗？

 

记录不合法的方案，考虑dp[i][j] ，下标为j，长度为i 的不可读的情况。

其实不可读的情况就是不经过结尾的结点即可。

 

最后答案就是利用26个字母，然后子节点通过父节点来累加答案。

 

最后把对立事件算出来即可。

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 const int N = 10005;
 8 const int M = 2e6+10;
 9 const int mod = 10007;
10 int Trie[M][26] , fail[M] , End[M], idx ;
11 int Q[M] , Head , Tail ;
12 int f[N][N];
13 int n ,m ;
14 
15 char str[N];
16 
17 void Insert( char s[] ){
18     int p = 0;
19     for(int i=0 ; s[i] ; i++ ){
20         int t = s[i] - ‘A‘ ;
21         if( !Trie[p][t] )
22             Trie[p][t] = ++idx ;
23         p = Trie[p][t];
24     }
25     End[p] |= 1  ;
26 }
27 
28 void Build(){
29     Head = 1 , Tail = 0 ;
30     for(int i=0;i<26;i++)
31         if(Trie[0][i])
32             Q[++Tail] = Trie[0][i] ;
33 
34     while( Head <= Tail ){
35         int u = Q[Head++] ;
36         for(int i=0;i<26;i++){
37             int To = Trie[u][i];
38             if( To ){
39                 fail[To] = Trie[fail[u]][i];
40                 Q[++Tail] = To;
41 
42                 End[To] |= End[fail[To]] ;
43             }else{
44                 Trie[u][i] = Trie[fail[u]][i];
45             }
46         }
47     }
48 
49 }
50 
51 void Solve(){
52     f[0][0] = 1 ;
53     for(int i=1;i<=m;i++){
54         for(int j=0;j<=idx;j++){
55             for(int k=0;k<26;k++){
56                 int To = Trie[j][k];
57                 if( !End[To] ){
58                     (f[i][To] += f[i-1][j]) %= mod ;
59                 }
60             }
61         }
62     }
63     int tot = 0 ;
64     for(int i=0;i<=idx;i++){
65         tot = (tot+f[m][i]) % mod ;
66     }
67     int sum = 1 ;
68     for(int i=1;i<=m;i++){
69         sum = sum * 26 % mod ;
70     }
71     printf("%d\n",(sum-tot+mod)%mod );
72 }
73 int main()
74 {
75     ios_base :: sync_with_stdio(false);
76     cin.tie(0) , cout.tie(0);
77     cin >> n >> m ;
78     for(int i=0;i<n;i++){
79         cin >> str ;
80         Insert(str);
81     }
82     Build();
83     Solve();
84     return 0 ;
85 }

View Code