0%

AC自动机

自动机

给定n个模式串和11个文本串,求有多少个模式串在文本串里出现过。(出现多次只算一次)

前置技能

1.Trie

2.KMP思想

1
2
3
4
5
6
7
8
struct note{
int son[26];//26个英文字母
int flag;//标记是否是末端
int fail;//fail指针
}trie[maxn];
int n,cnt;
string s;
queue<int>q;

我们将n个模式串建成一颗Trie树,建树的方式和建Trie完全一样

1
2
3
4
5
6
7
8
9
10
11
12
void insert(string s)//构建trie
{
int u=1;
for(int i=0;i<s.length();++i)
{
int v=s[i]-'a';
if(!trie[u].son[v])
trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag++;
}

img

假如我们现在有文本串ABCDBC

我们用文本串在Trie上匹配,刚开始会经过2、3、4号点,发现到4,成功匹配了一个模式串,然后就不能在继续匹配了,这时我们还要重新从根开始匹配吗?

这样效率太慢了。这时我们就要借用KMP的思想,从Trie上的某个点继续匹配

这时我们就应该确定从哪个点继续匹配?我们称i匹配失败后继续从j开始匹配,j是i的Fail(失配指针)

求Fail

首先我们可以确定,每一个点i的Fail指针指向的点的深度一定是比i小的。(Fail指的是后缀啊)

第一层的Fail一定指的是root。(比深度11还浅的只有root了)

设点i的父亲fa的Fail指针指的是fafail,那么如果fafail有和i值相同的儿子j,那么i的Fail就指向j。这里可能比较难理解一点,建议画图理解,不过等会转换成代码就很好理解了。

由于我们在处理i的情况必须要先处理好fa的情况,所以求Fail我们使用BFS来实现。

实现的一些细节

  • 1、刚开始我们不是要初始化第一层的fail指针为root,其实我们可以建一个虚节点00号节点,将00的所有儿子指向root(root编号为11,记得初始化),然后root的fail指向00就OK了。效果是一样的。
  • 2、如果不存在一个节点i,那么我们可以将那个节点设为fafail的**((值和i相同)的儿子)**。保证存在性,就算是00也可以成功返回到根,因为00的所有儿子都是根。
  • 3、无论fafail存不存在和i值相同的儿子j,我们都可以将i的fail指向j。因为在处理i的时候j已经处理好了,如果出现这种情况,j的值是第22种情况,也是有实际值的,所以没有问题。
  • 4、实现时不记父亲,我们直接让父亲更新儿子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void getFail()
{
for(int i=0;i<26;++i)
trie[0].son[i]=1;//初始化0的所有儿子都是0
q.push(1);//将根节点压入队列
trie[1].fail=0;//1为root,将1的fail指向0
while(!q.empty())//bfs
{
int u=q.front();
q.pop();
for(int i=0;i<26;++i)
{
int v=trie[u].son[i];//其子节点
int Fail=trie[u].fail;
if(!v)//表示不存在该节点
{
trie[u].son[i]=trie[Fail].son[i];
continue;
}
trie[v].fail=trie[Fail].son[i];
q.push(v);//存在实节点就压入队列
}
}
}

完整代码:

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct note{
int son[26];//26个英文字母
int flag;//标记是否是末端
int fail;//fail指针
}trie[maxn];
int n,cnt;
string s;
queue<int>q;

void insert(string s)//构建trie
{
int u=1;
for(int i=0;i<s.length();++i)
{
int v=s[i]-'a';
if(!trie[u].son[v])
trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag++;
}

void getFail()
{
for(int i=0;i<26;++i)
trie[0].son[i]=1;//初始化0的所有儿子都是0
q.push(1);//将根节点压入队列
trie[1].fail=0;//1为root,将1的fail指向0
while(!q.empty())//bfs
{
int u=q.front();
q.pop();
for(int i=0;i<26;++i)
{
int v=trie[u].son[i];//其子节点
int Fail=trie[u].fail;
if(!v)//表示不存在该节点
{
trie[u].son[i]=trie[Fail].son[i];
continue;
}
trie[v].fail=trie[Fail].son[i];
q.push(v);//存在实节点就压入队列
}
}
}

int query(string s)
{
int u=1,ans=0;
for(int i=0;i<s.length();++i)
{
int v=s[i]-'a';
int k=trie[u].son[v];
while(k>1&&trie[k].flag!=-1)
{
ans+=trie[k].flag;
trie[k].flag=-1;//标记已经找过了
k=trie[k].fail;
}
u=trie[u].son[v];//到下一个儿子
}
return ans;
}

int main()
{
cnt=1;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>s;
insert(s);
}
getFail();
cin>>s;
cout<<query(s)<<endl;
}