P3796 【模板】AC自动机（加强版）

博主个人链接

题目链接

题意：

求出主串中出现次数最多的模式串

题解：

用AC自动机将所有模式串建Trie图，然后拿主串去跑Trie图得出模式串cnt数组排序输出

代码：

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