【AC自动机】洛谷 P3808 【模板】AC自动机（简单版）

题链

题目分析

多模式串匹配，使用$AC$自动机，模板题；

学自 $OI-wiki$

代码实现

#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ULL unsigned long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define B1 131
	#define B2 13331
	#define M1 1000000007
	#define M2 1000000009
	#define eps 1e-8
	#define MAXN 9e18
	#define MS 1000009

//  for(int j=u;j && ext[j];j=fail[j])

int n,m,k;
char s[MS];
int dic[MS][26], ext[MS], fail[MS], tot;
queue<int > Q;

void insert(char *s, int len){
	int u = 0;
	for(int i=0;i<len;i++){
		int c = s[i]-'a';
		if(!dic[u][c]) dic[u][c] = ++tot;
		u = dic[u][c];
	} 
	ext[u]++;
}

void build(){
	for(int i=0;i<26;i++){
		if(dic[0][i]) Q.push(dic[0][i]);
	} 
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		for(int i=0;i<26;i++){
			if(dic[u][i]){
				fail[dic[u][i]] = dic[fail[u]][i];
				Q.push(dic[u][i]);
			}
			else{
				dic[u][i] = dic[fail[u]][i];
			}
		}
	}
}

int query(char *s, int len){
	int cnt = 0;
	for(int i=0,u=0,c;i<len;i++){
		c = s[i]-'a';
		u = dic[u][c];
		for(int j=u;j && ext[j];j=fail[j]){
			cnt += ext[j];
			ext[j] = 0;
		}
	} 
	return cnt;
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> s;
		insert(s, strlen(s)); 
	} 
	build();
	cin >> s;
	cout << query(s, strlen(s)) << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
	//cin >> ce;
	while(ce--){
		solve();
	}
}