【模板】AC 自动机（二次加强版）
题目传送门
题目大意
给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$ ，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。
当时写题过程
当时看到题目后，看着和前面一个模板题一模一样，于是，就直接把前面一个的代码 copy 了过来，交了一发，出现了第一幕，40分，里面不是 WA 就是 TLE ，我想不通为什么会有 WA ，于是，我又重新读了一遍题，发现这道题里面 数据不保证任意两个模式串不相同 。
我想先保证算法的正确性，然后再进行优化操作，于是，把这里改了一下之后，就又交了一发，果然，这一发里面就只有 TLE 了，那么问题来了，该怎么优化呢。
当时想到了在匹配的过程中不进行答案的汇总，而是只进行汇总 Trie 树里面的每个节点到过的次数，等匹配结束之后再总的进行答案的汇总。果然，这次 TLE 的测试点数就少了好多，但是仍然无法AC。
之后，我又想到了在 bfs() 中把每个 Trie 树的节点所对应的单词汇总，这样就不需要每次都往根部递归求值了，结果，测试点中终于没有 TLE 了，但是，又出现了三个 MLE ，每个 Trie 树节点存的单词数量太大了，这个方法也行不通。
最后，我就想，有没有一种可能，我可以记录他在 bfs() 的过程中的 bfs 序，然后，在匹配的过程中只记录每个节点到过的次数，最后，在匹配结束之后，利用 bfs 序的逆序进行遍历，每遍历一个点，就把这个点往根部递归的第一个点的访问次数加上这个点的访问次数，以此递推，即可得出答案数组。
思路
首先，在匹配的过程中，我们只需要记录每个点的访问次数，这里用 $nnum$ 数据进行记录。在匹配结束之后，为了防止递归式的求解(因为这样会一直重复访问一些(数据量非常大)节点)，我们需要遍历一遍就能求解出答案的方法。于是，我们需要一个特殊的遍历序列，这个序列需要满足后遍历的节点在递归的思路里面不会到达先遍历的节点，而且先遍历的节点需要能够把他的访问次数传递到他在递归的思路中到达的后遍历的节点。刚好，我们在 bfs() 的过程的序列刚好就是这个序列的逆序列。于是，我们记录下来在 bfs() 过程中的访问顺序，在最后求解答案的时候再逆序访问即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
| #include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#include<unordered_set>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<P,int> PP;
const int MAXX=2000005;
const double eps=0.0000001;
const LL mod=998244353;
const int id_max=MAXX;
int n,flag[id_max],fail[id_max];
int trie[id_max][26],id_cnt;
vector<int> id[id_max];
char s[MAXX];
int num[MAXX];
void init(){
id_cnt=0;
for(int i=0;i<id_max;++i){
flag[i]=fail[i]=0;
id[i].clear();
for(int j=0;j<26;++j)
trie[i][j]=0;
}
}
void ins(char s[]){
int len=strlen(s+1);
int now=0;
for(int i=1;i<=len;++i){
if(trie[now][s[i]-'a']==0)
trie[now][s[i]-'a']=++id_cnt;
now=trie[now][s[i]-'a'];
}
++flag[now];
}
void ins(char s[],int idd){
int len=strlen(s+1);
int now=0;
for(int i=1;i<=len;++i){
if(trie[now][s[i]-'a']==0)
trie[now][s[i]-'a']=++id_cnt;
now=trie[now][s[i]-'a'];
}
id[now].emplace_back(idd);
}
int bfsn[id_max];
void bfs(){
queue<int> qq;
for(int i=0;i<26;++i)
if(trie[0][i])
qq.emplace(trie[0][i]);
int bfs_cnt=0;
while(!qq.empty()){
int now=qq.front();qq.pop();
bfsn[++bfs_cnt]=now;
for(int i=0;i<26;++i){
if(trie[now][i]){
fail[trie[now][i]]=trie[fail[now]][i];
qq.emplace(trie[now][i]);
}
else
trie[now][i]=trie[fail[now]][i];
}
}
}
int getone(char s[]){
int now=0,len=strlen(s+1);
int ret=0;
for(int i=1;i<=len;++i){
now=trie[now][s[i]-'a'];
int jj=now;
while(jj>0&&flag[jj]!=-1){
ret+=flag[jj];
flag[jj]=-1;
jj=fail[jj];
}
}
return ret;
}
int nnum[id_max];
void getnum(char s[]){
memset(num,0,sizeof(num));
int now=0,len=strlen(s+1);
for(int i=1;i<=len;++i){
now=trie[now][s[i]-'a'];
++nnum[now];
}
}
inline void solve_it(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
getchar();
scanf("%s",s+1);
ins(s,i);
}
bfs();
getchar();scanf("%s",s+1);
getnum(s);
for(int i=id_cnt;i>0;--i){
int now=bfsn[i];
nnum[fail[now]]+=nnum[now];
int si=id[now].size();
for(int j=0;j<si;++j)
num[id[now][j]]+=nnum[now];
}
for(int i=1;i<=n;++i){
printf("%d\n",num[i]);
}
}
signed main(){
solve_it();
return 0;
}
|
总结
这道题的变数感觉好多，当时写完这道题之后我去翻了翻题解，发现并没有我这样的写法，题解中的写法各式各样，思路众多，以后写这类题目一定要从多个方面进行思考。
