AC自动机
所谓AC自动机，其实是kmp算法与字典树的结合,不懂这两个，是无法学会的。 # 自动机 自动机，是一个五元组，包括了状态的非空有穷集合，符号的有限集合，状态转移函 数， 开始状态，终止状态集合，而在字典树上，增加了两个新的东西，一个标记了终止状态集合，另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态，而边则用来表示状态转移函数的一部分。
匹配
当AC自动机建立好了以后，我们就可以在AC自动机上进行匹配了，我们在自动机上一 个一个 节点忘下跑，一直到失配，即到达AC自动机上某个节点后，此节点所代表的字符串，与母串的当前前缀子串相差刚好只为最后一个字母，这 时候，我们跳跃到fail指针即可进行后面的继续匹配。 # file指针 fail指针当然跳得越深越好，这时候fail所代表的意义到底是什么呢？很明显，此时 要求与母串有 尽可能长得公共前缀，也就是说与失配发生的时候AC自动机所在节点（所表示的状态）表示的字符串的尽可能长的后缀相同的新节点 ， 这里我们明显可以采取树形dp来得到。 # 内存开销 我们用fail[u]表示节点u的失配指针，用nex[u][i]表示节点u的指向 字符i的节点， 于是我们发现 了转移式子： fail[nex[u][i]]= nex[fail[u]][i];如果fail[u]有儿子i的话，但如果没有呢？我们又要不断往上面跳跃对吧。 复杂度不是特别高，能忍受，当然这是在u有节点i的情况下。如果没有节点呢？sorry，这个问题有点复杂，一般的AC自动机不关心这种事情。因为那 会增加很多额外的开销，我们不愿意去给他们建立新节点来储存fail指针的。 # 字典图 有一种AC自动机，他索性把字典树建成了字典图，如果nex指针指向空节点，他 一定会导致失配，他的nex指针就直接指向了应该是fail指针的地方，很漂亮的做法，但是我们失去了很多，比方说，树没有了，AC自动机不能再加入新 的模式串了。这让我们很难受，抉择产生了，要么选择字典树+好几倍的新空间开销，要么选择字典图。 # 更好的解决方案 笔者对此思考了很久，很久，考虑到我们要么用-1要么用0来表示nex指针指向的 是空节点，也就是说，负数没有被使用到，我们可以这样做，如果一条边在字典树上，我们正常储存，如果他不在字典树，而是在字典图上，那我们存储 他所指向的节点的相反数，一者表示此指针指向空节点，再者表示此指针指向的节点的fail指针，这样的做法集合了上诉两种做法的优点于一身。下面是我的代码。
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
| struct Aho_Corasick_automation{
static const int maxn=1e6+5;
int trans[maxn][26],fail[maxn],end[maxn];
int root,cnt;
inline int new_node(){
for(int i=0;i<26;i++)trans[cnt][i]=0;
end[cnt]=0;
return cnt++;
}
void ini(){
cnt=0;
root=new_node();
}
void extend(char*buf){
int len=(int)strlen(buf+1);
int u=root;
for(int i=1;i<=len;i++){
if(trans[u][buf[i]-'a']==0)
trans[u][buf[i]-'a']=new_node();
u=trans[u][buf[i]-'a'];
}
end[u]++;
}
void get_fail(){
queue<int>q;
q.push(root);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(trans[u][i]==0){
trans[u][i]=-abs(trans[fail[u]][i]);
}
else{
q.push(trans[u][i]);
fail[trans[u][i]]=abs(trans[fail[u]][i]);
if(u==root)fail[trans[u][i]]=root;
}
}
}
}
int query(char*buf){
int len=(int)strlen(buf+1);
int u=root ,ret=0;
for(int i=1;i<=len;i++){
u=abs(trans[u][buf[i]-'a']);
for(int p=u;p!=root;p=fail[p]){
if(end[p]==-1)break;
ret+=end[p];
end[p]=-1;
}
}
return ret;
}
void debug(){
for(int i=0;i<35;i++)printf(" ");
for(int j=0;j<26;j++){
printf("%2c",j+'a');
}
puts("");
for(int i=0;i<cnt;i++){
printf("id=%3d | fail=%3d | end=%3d | chi=[",i,fail[i],end[i]);
for(int j=0;j<26;j++){
printf("%2d",trans[i][j]);
}
printf("]\n");
}
}
};
|