【AC自动机】洛谷 P3796 【模板】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

// P3796 【模板】AC自动机（加强版） 
// for(int j=u;j;j=fail[j])

int n,m,k;
struct node{
	char s[100];
}p[200];
int cnt[200];
char s[MS];
int dic[MS][26], ext_id[MS], fail[MS], tot;
queue<int > Q;

void insert(char *s, int len, int id){
	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_id[u] = id;
}

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];
			}
		}
	}
}

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

void clear(){
	memset(cnt, 0, sizeof cnt);
	memset(dic, 0, sizeof dic);
	memset(ext_id, 0, sizeof ext_id);
	memset(fail, 0, sizeof fail);
	tot = 0;
}

void solve(){
	for(int i=1;i<=n;i++){
		cin >> p[i].s;
		insert(p[i].s, strlen(p[i].s), i); 
	} 
	build();
	cin >> s;
	query(s, strlen(s));
	int maxn = 0;
	for(int i=1;i<=n;i++) maxn = max(maxn, cnt[i]);
	cout << maxn << "\n";
	for(int i=1;i<=n;i++){
		if(cnt[i] == maxn){
			cout << p[i].s << "\n"; 
		}
	}
	clear();
}

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