AC自动机

应用场景

多模式匹配问题

多串匹配一个串

预定义

1
2
3
4
5
6
7
8
9
const int N = 1e6+100;
char s[N],m[N];
struct node
{
int son[26];
int fail;
int count;
}ac[N];
int tot = 0;

初始化

1
2
3
4
5
6
7
8
9
10
// 涉及多组时需要用到
void init()
{
for(int i = 0;i < N;i++)
{
memset(ac[i].son,0,sizeof ac[i].son);
ac[i].count = 0;
ac[i].fail = 0;
}
}

插入单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Insert(char *s)
{
int len = strlen(s);
int now = 0;
int tmp;
for(int i = 0;i < len;i++)
{
tmp = s[i]-'a';
if(ac[now].son[tmp] == 0)
ac[now].son[tmp] = ++tot;
now = ac[now].son[tmp];
}
ac[now].count++;
}

构造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
void MakeFail()
{
queue<int> q;
for(int i = 0;i < 26;i++)
{
if(ac[0].son[i] != 0)
{
ac[ac[0].son[i]].fail = 0;
q.push(ac[0].son[i]);
}
}
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0;i < 26;i++)
{
if(ac[u].son[i] != 0)
{
ac[ac[u].son[i]].fail = ac[ac[u].fail].son[i];
q.push(ac[u].son[i]);
}
else
ac[u].son[i] = ac[ac[u].fail].son[i];
}
}
}

AC自动机匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Query(char *s)
{
int len = strlen(s);
int now = 0,ans = 0,tmp;
for(int i = 0;i < len;i++)
{
tmp = s[i]-'a';
now = ac[now].son[tmp];
for(int t = now;t && ac[t].count != -1;t = ac[t].fail)
{
ans += ac[t].count;
ac[t].count = -1;
}
}
return ans;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
Insert(s);
}
ac[0].fail = 0; // 切记
MakeFail();
scanf("%s",m);
printf("%d\n",Query(m));
return 0;
}

练手题目

P3808 【模板】AC自动机(简单版)

Keywords Search