HeinzHuang

Eudaimonia

0%

AC自动机

Posted on Edited on In

若不熟悉KMP算法，强烈建议好好先去了解一下，否则这里会有很多不大理解的思想。

Trie树上的KMP?

想想原本的\(KMP\)算法，为了快速匹配，我们根据匹配串先预处理一个\(next[]\)数组，也就是最长的后缀与前缀完全匹配的位置，然后一旦遇到匹配错误的时候，就把当时的匹配指针移到他的\(next[]\)即可。

那么想想，如果有多个匹配串和一个文本串，要求你在文本串中找出能匹配到多少个串。那么想想，如果关于所有匹配串建立一颗\(Trie\)树，在这个上面进行\(KMP\)算法是否可行呢？

例题：

Keywords Search （HDU-2222）

题目描述

czh在成千上万次尝试后，终于被自己感动了，他决定换一种方式来理解cry的文章，他列举出自己掌握的所有单词，来统计词频，可是czh已经累了，不想动了，只能瘫在椅子上给你们加油了。

输入

第一行一个正整数表示数据组数 每组第一行一个正整数N表示czh掌握的单词数量N<=10000 接下来每行一个字符串表示掌握的单词，每个单词只包含小写字母，长度不超过50 最后一行为文章字符串，长度不超过1000000

输出

每组数据输出一行，每行一个数字表示文章中出现了几个czh掌握的单词。

样例输入

1
2
3
4
5
6
7
8
1
5
ate
at
eat
tea
year
hyeateart

样例输出

1
4

思路：

这是一道AC自动机的裸题。就像前面所说的在\(Trie\)树上进行\(KMP\)匹配。那么首先自然就是\(Trie\)树的建立。写法如下（当然，不是唯一写法） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node{
	void init(){loop(i,26)son[i]=0;cnt=0;fail=0;}
	int son[26],cnt,fail;
}T[M];
void insert(char str[]){
	int len=strlen(str);
	int cur=0;
	loop(i,len){
		int x=str[i]-'a';
		if(!T[cur].son[x])T[cur].son[x]=++sz,T[sz].init();
		cur=T[cur].son[x];
	}
	T[cur].cnt++;
}
接下来就是AC自动机的精髓了，就是fail数组的预处理了。\(fail\)数组就是\(KMP\)算法中的\(next\)数组。由于每个从\(Trie\)树根到某一个节点都对应一个前缀，那么如果匹配失败的话就跳回后缀与前缀相等的最大长度的位置。那么预处理fail则是如此： 
1
T[T[x].son[i]].fail=T[T[x].fail].son[i];
但是如果\(T[x].son[i]\)为空的话，那么就把他指向他的\(fail\)位置的儿子： 
1
T[x].son[i]=T[T[x].fail].son[i];
经过这样的操作，若是对一个文本串的预处理，就只需要跳他的儿子即可。

最后就是遍历\(Trie\)树的顺序，只需要用一个队列进行类\(bfs\)操作即可。 

1
2
3
4
5
6
7
8
9
10
void ac_automation(){
	loop(i,26)if(T[0].son[i])T[T[0].son[i]].fail=0,Q.push(T[0].son[i]);//将根节点的儿子推进队列
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		loop(i,26){
			if(T[x].son[i])T[T[x].son[i]].fail=T[T[x].fail].son[i],Q.push(T[x].son[i]);
			else T[x].son[i]=T[T[x].fail].son[i];
		}
	}
}
这个写法比较，不过个人认为我的写法是比较简单的，仔细理解。

最后就是对文本串的匹配，每次直接跳儿子，每次若是遇到一个匹配串的结尾，就将其计入答案，同时每次跳\(fail\)节点的时候，将其标记掉没下次就不跳了，因为跳过后所有可能的点都已被计入答案了，于是最终代码便是如此： 

1
2
3
4
5
6
7
8
9
int Query(){
	int len=strlen(S);
	int cur=0,ans=0;
	loop(i,len){
		cur=T[cur].son[S[i]-'a'];
		for(int j=cur;j&&~T[j].cnt;j=T[j].fail)ans+=T[j].cnt,T[j].cnt=-1;
	}
	return ans;
}
那么这样这道题就做出来了，总体还是比较简单的，最终代码如下：

代码

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
#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=l,END=r;i<=END;i++)
#define DOR(i,r,l) for(int i=r,END=l;i>=END;i--)
#define loop(i,n) for(int i=0,END=n;i<END;i++)
#define sf scanf
#define pf printf
#define mms(a,x) memset(a,x,sizeof a)
using namespace std;
const int M=1e6+5;
int n;
char str[M],S[M];
struct Trie{
	int sz;
	queue<int>Q;
	struct node{
		void init(){loop(i,26)son[i]=0;cnt=0;fail=0;}
		int son[26],cnt,fail;
	}T[M];
	void insert(char str[]){//插入匹配串
		int len=strlen(str);
		int cur=0;
		loop(i,len){
			int x=str[i]-'a';
			if(!T[cur].son[x])T[cur].son[x]=++sz,T[sz].init();
			cur=T[cur].son[x];
		}
		T[cur].cnt++;
	}
	void ac_automation(){//预处理fail
		loop(i,26)if(T[0].son[i])T[T[0].son[i]].fail=0,Q.push(T[0].son[i]);
		while(!Q.empty()){
			int x=Q.front();Q.pop();
			loop(i,26){
				if(T[x].son[i])T[T[x].son[i]].fail=T[T[x].fail].son[i],Q.push(T[x].son[i]);
				else T[x].son[i]=T[T[x].fail].son[i];
			}
		}
	}
	int Query(){//查询答案
		int len=strlen(S);
		int cur=0,ans=0;
		loop(i,len){
			cur=T[cur].son[S[i]-'a'];
			for(int j=cur;j&&~T[j].cnt;j=T[j].fail)ans+=T[j].cnt,T[j].cnt=-1;//标记掉路径
		}
		return ans;
	}
	void init(){
		sz=0;
		T[0].init();
	}
}Tr;
int main(){
	int T;
	sf("%d",&T);
	while(T--){
		Tr.init();
		sf("%d",&n);
		FOR(i,1,n){
			sf("%s",str);
			Tr.insert(str);
		}
		Tr.ac_automation();
		sf("%s",S);
		pf("%d\n",Tr.Query());
	}
	return 0;
}