AC 自动机笔记

模板代码（P3808 AC 自动机（简单版））

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
#include<bits/stdc++.h>
using namespace std;
int n,tot,cnt[1000005],ch[1000005][30],ne[1000005];
void insert(string s){
	int u=0;
	for(char c:s){
		int v=c-'a';
		if(!ch[u][v])ch[u][v]=++tot;
		u=ch[u][v];
	}
	cnt[u]++;
}
void build(){
	queue<int>q;
	for(int i=0;i<26;++i){
		if(ch[0][i])q.push(ch[0][i]);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			int v=ch[u][i];
			if(v)ne[v]=ch[ne[u]][i],q.push(v);
			else ch[u][i]=ch[ne[u]][i];
		}
	}
}
int query(string s){
	int ans=0;
	for(int k=0,i=0;s[k];k++){
		i=ch[i][s[k]-'a'];
		for(int j=i;j&&~cnt[j];j=ne[j]){
			ans+=cnt[j],cnt[j]=-1;
		}
	}
	return ans;
}
string t;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		string s;
		cin>>s;
		insert(s);
	}
	cin>>t;
	build();
	cout<<query(t);
	return 0;
}