新手天翼
新手天翼
一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。
要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。
如果你对KMP算法了解的话，应该知道KMP算法中的next函数（shift函数或者fail函数）是干什么用的。KMP中我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符，当A[i+1]≠B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配，而next函数恰恰记录了这个j应该调整到的位置。同样AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Trie上进行匹配时，如果与当前节点的关键字不能继续匹配，就应该去当前节点的失败指针所指向的节点继续进行匹配。
案例
Problem Description
In the modern time, Search engine came into the life of everybody.Wiskey also wants to bring this feature to his image retrieval system.Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched. To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
The last line is the description, and the length will be not longer than1000000.
Output
Print how many keywords are contained in the description.
自动机 C++ 源代码
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
#include<iostream>
using namespace std;
const int kind=26;
struct node{
node *fail;//失败指针
node *next[kind];//Trie每个节点的26个子节点（最多26个字母）
int count;//是否为该单词的最后一个节点
node(){//构造函数初始化
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
} *q[1000000];//队列，方便用于bfs构造失败指针
char keyword[51];//输入的单词
char str[1000001];//模式串
~~~~~~~~~~~~~~~~~~~~~~~~
自动机Pascal模块
POJ1204（AC自动机模板题）
题意：给一个N行长为M的字符串，给你一些需要去匹配的字符串，从任意一个字符串开始可以有八个方向，向上为A，顺时针依次是A——H，问你去匹配的字符串在给你的N*M字符串中的坐标是怎么样的。
代码：
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
const
maxnodes=500000;
var
fx:array[1..8]of char=('E','F','G','H','A','B','C','D');
t:array[0..maxnodes,'A'..'Z']of longint;
f,q,w:array[0..maxnodes]of longint;
e:array[0..1001,0..1001]of char;
s:array[0..1001]of char;
colu,line:array[0..1]of longint;
done:array[0..1001]of boolean;
ans:array[0..1001]of record
x,y,f:longint;
end;
n,m,num,u,i,j,k,l,r,root,size,x,y,p,li,co,tmp,len:longint;
c:char;
function nx(varx,y:longint;f:longint):char;
begin
case f of
1:dec(x);
2:begin
dec(x);
inc(y);
end;
3:inc(y);
4:begin
inc(x);
inc(y);
end;
5:inc(x);
6:begin
inc(x);
dec(y);
end;
7:dec(y);
8:begin
dec(x);
dec(y);
end;
end;
if(x<1)or(x>n)or(y<1)or(y>m)then
exit('!');
exit(e[x,y]);
end;
begin
readln(n,m,num);
line[0]:=1;
line[1]:=n;
colu[0]:=1;
colu[1]:=m;
for i:=1 to n do begin
for j:=1 to m do read(e[i,j]);
readln;
end;
root:=0;
size:=0;
for i:=1 to num do begin
len:=0;
while not eoln do begin
inc(len);
read(s[len]);
end;
p:=root;
for j:=len downto 1 do begin
c:=s[j];
if t[p,c]=0 then begin
inc(size);
t[p,c]:=size;
end;
p:=t[p,c];
end;
inc(r);
q[r]:=t[root,c];
f[q[r]]:=root;
end;
while l<r do begin
inc(l);
u:=q[l];
for c:='A' to 'Z' do
if t[u,c]<>0 then begin
inc(r);
q[r]:=t[u,c];
p:=f[u];
while(p<>root)and(t[p][c]=0)do
p:=f[p];
f[q[r]]:=t[p,c];
end;
end;
for k:=1 to 8 do
for li:=0 to 1 do
for co:=1 to m do begin
x:=line[li];
y:=co;
p:=root;
c:=e[x,y];
while true do begin
while(p<>root)and(t[p][c]=0)do
p:=f[p];
p:=t[p,c];
tmp:=p;
while tmp<>root do begin
if(w[tmp]>0)and(not done[w[tmp]])then begin
ans[w[tmp]].x:=x;
ans[w[tmp]].y:=y;
ans[w[tmp]].f:=k;
done[w[tmp]]:=true;
end;
tmp:=f[tmp];
end;
c:=nx(x,y,k);
if c='!' then
break;
end;
end;
for k:=1 to 8 do for co:=0 to 1 do for li:=1 to n do begin
x:=li;
y:=colu[co];
p:=root;
c:=e[x,y];
while true do begin
while(p<>root)and(t[p,c]=0)do
p:=f[p];
p:=t[p,c];
tmp:=p;
while tmp<>root do begin
if(w[tmp]>0)and(not done[w[tmp]])then begin
ans[w[tmp]].x:=x;
ans[w[tmp]].y:=y;
ans[w[tmp]].f:=k;
done[w[tmp]]:=true;
end;
tmp:=f[tmp];
end;
c:=nx(x,y,k);
if c='!'then
break;
end;
end;
for i:= 1 to num do
writeln(ans[i].x-1,' ',ans[i].y-1,' ',fx[ans[i].f]);
end.
高级光能
请先打牢基础，因为你就算知道了也没用。
如果你求知欲真的很强，请 @陆麟瑞 @樊澄宇
贾文卓在2018-10-19 22:49:04追加了内容
@蒋智航 就算有用，也得先进省选才有用......
新手光能
什么AC自动机，我只知道WA自动机和TLE自动机；
中级天翼
1
