AC自动机模板

博主链接

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 1000050
#define max_tot 500050
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 7;
struct Ac {
	struct state {  //节点状态
		int next[26];
		int fail, cnt;//指针fail 到这个节点有cnt个串结束
	}stable[max_tot];
	int size;  //当前AC自动机节点个数
	queue<int>q;
	void init() {  //初始化
		met(stable);
		size = 1;
		while (!q.empty())q.pop();
	}
	void insert(char *s) {  //将模式串插入trie树
		int now = 0; //代表走到那个节点
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (!stable[now].next[ch])  //节点不存在该字母边，则新建一个
				stable[now].next[ch] = size++;
			now = stable[now].next[ch];
		}
		stable[now].cnt++;//结束位置++；
	}
	void build() {  //构造失配fail指针，要构造当前节点fail指针需先构造爸爸节点
		for (int i = 0; i < 26; i++)if (stable[0].next[i])q.push(stable[0].next[i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (stable[u].next[i]) {  //如果有i这条边 枚举下他儿子
						int v = stable[u].fail;
						int a = stable[u].next[i];
						while (v) {  //一直按箭头的fail
							if (stable[v].next[i]) {  //如果他某个祖先有i这条边
								stable[a].fail = stable[v].next[i];
								break;
							}
							v = stable[v].fail;
						}
						if (!stable[a].fail)stable[a].fail = stable[0].next[i];
						q.push(stable[u].next[i]);  //节点加进去
				}
			}
		}
	}
	int get(int u) {  //算所有祖先的和
		int res = 0;
		while (u) {
			res = res + stable[u].cnt;
			stable[u].cnt = 0;  //计算后不再计算，如果要计算不清零
			u = stable[u].fail;
		}
		return res;
	}
	int match(char *s) {   //匹配
		int res = 0, now = 0;
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (stable[now].next[ch])  //如果当前状态太能找到后继节点，则走他
				now = stable[now].next[ch];
			else {  //否则只能跳爸爸
				int p = stable[now].fail;
				while (p && stable[p].next[ch] == 0)p = stable[p].fail; //始终没找到，只能指根节点 //找到就跳对应地方
				now = stable[p].next[ch];
			}
			if (stable[now].cnt)res = res + get(now);//
		}
		return res;
	}
}Ac;
char s[max_n];
int main(int argc, char *argv[]) {
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
}

应用：查找母串中各单词出现次数–对应题目P3796

/* 有 N 个由小写字母组成的模式串以及一个文本串 TT 。每个模式串可能会在文本串中出现多次。 你需要找出哪些模式串在文本串 T 中出现的次数最多。 输入输出格式 输入格式： 输入含多组数据。 每组数据的第一行为一个正整数 N ，表示共有 NN 个模式串1≤N≤150 。 接下去 N 行，每行一个长度小于等于70 的模式串。下一行是一个长度小于等于1e6的文本串 TT 。 输入结束标志为 N=0 。 输出格式： 对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。 输入输出样例 输入样例#1： 2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0 输出样例#1 4 aba 2 alpha haha https://www.luogu.org/problemnew/show/P3796 */
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 1000050
#define max_tot 500050
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 7;
struct aa {
	int i;
	int cnt;
}ans[180];
int cmp(aa a, aa b) {
	if (a.cnt == b.cnt)return a.i < b.i;
	else return a.cnt > b.cnt;
}
struct Ac {
	struct state {  //节点状态
		int next[26];
		int fail, cnt;//指针fail 到这个节点有cnt个串结束
	}stable[max_tot];
	int size;  //当前AC自动机节点个数
	queue<int>q;
	void init() {  //初始化
		met(stable);
		size = 1;
		while (!q.empty())q.pop();
		for (int i = 0; i <= 150; i++) {
			ans[i].i = i;
			ans[i].cnt = 0;
		}
	}
	void insert(char *s,int n) {  //将模式串插入trie树
		int now = 0; //代表走到那个节点
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (!stable[now].next[ch])  //节点不存在该字母边，则新建一个
				stable[now].next[ch] = size++;
			now = stable[now].next[ch];
		}
		stable[now].cnt=n;//结束位置++；
	}
	void build() {  //构造失配fail指针，要构造当前节点fail指针需先构造爸爸节点
		for (int i = 0; i < 26; i++)if (stable[0].next[i])q.push(stable[0].next[i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (stable[u].next[i]) {  //如果有i这条边 枚举下他儿子
						int v = stable[u].fail;
						int a = stable[u].next[i];
						while (v) {  //一直按箭头的fail
							if (stable[v].next[i]) {  //如果他某个祖先有i这条边
								stable[a].fail = stable[v].next[i];
								break;
							}
							v = stable[v].fail;
						}
						if (!stable[a].fail)stable[a].fail = stable[0].next[i];
						q.push(stable[u].next[i]);  //节点加进去
				}
			}
		}
	}
	void get(int u) {  //算所有祖先的和
		int res = 0;
		u = stable[u].fail;
		while (u) {
			if(stable[u].cnt)ans[stable[u].cnt].cnt++;  //找个数
			u = stable[u].fail;
		}
		return;
	}
	int match(char *s) {   //匹配
		int res = 0, now = 0;
		for (int i = 0; s[i]; i++) {
			char ch = s[i]-'a';
			if (stable[now].next[ch])  //如果当前状态太能找到后继节点，则走他
				now = stable[now].next[ch];
			else {  //否则只能跳爸爸
				int p = stable[now].fail;
				while (p && stable[p].next[ch] == 0)p = stable[p].fail; //始终没找到，只能指根节点 //找到就跳对应地方
				now = stable[p].next[ch];
			}
			if (stable[now].cnt) { 
				ans[stable[now].cnt].cnt++; 
			}
			get(now);
			
		}
		return res;
	}
}Ac;
char s[max_n];
char s1[200][80];
int main(int argc, char *argv[]) {
	/*ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);*/
	int t, n;
	while (scanf("%d", &n)&&n!=0) {
		Ac.init();
		for (int i = 1; i <= n; i++) {
			scanf("%s", s1[i]);
			Ac.insert(s1[i], i);
		}
		Ac.build();

		scanf("%s", s);
		Ac.match(s);

		sort(ans, ans + n+1, cmp);
		printf("%d\n", ans[0].cnt);
		printf("%s\n", s1[ans[0].i]);
		for (int i = 1; i < n; i++) {
			if (ans[i].cnt == ans[0].cnt)printf("%s\n", s1[ans[i].i]);
			else break;
		}
	}
	return 0;
}