AC自动机（加强版）洛谷P3796

有 NN 个由小写字母组成的模式串以及一个文本串 TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 TT 中出现的次数最多。

输入含多组数据。保证输入数据不超过 5050 组。

每组数据的第一行为一个正整数 NN，表示共有 NN 个模式串，1 leq N leq 1501≤N≤150。

接下去 NN 行，每行一个长度小于等于 7070 的模式串。下一行是一个长度小于等于 10^6106 的文本串 TT。保证不存在两个相同的模式串。

输入结束标志为 N=0N=0。

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入 #1

2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

输出 #1

4
aba
2
alpha
haha

题意： n个模式串，1个文本串，输出出现次数最多的模式串，如果有多个，按照出现顺序输出。

分析： ac自动机模板，值得注意的是记录出现次数时可以直接用map，也可以记录这个字符串在trie上的节点编号，通过桶来记录次数，显然后者效率会更高。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int cnt[10505], son[10505][26], fail[10505], idx;
string query[155];
string text;
unordered_map mp;

void insert(int x)
{
	int now = 0, len = query[x].size();
	for(int i = 0; i < len; i++)
	{
		int t = query[x][i]-'a';
		if(!son[now][t])
			son[now][t] = ++idx;
		now = son[now][t];
	}
	cnt[now] = len;
}

void GetFail()
{
	queue q;
	for(int i = 0; i < 26; i++)
		if(son[0][i])
			q.push(son[0][i]);
	while(q.size())
	{
		int now = q.front(), fafail = fail[now];
		q.pop();
		for(int i = 0; i < 26; i++)
		{
			if(son[now][i])
			{
				fail[son[now][i]] = son[fafail][i];
				q.push(son[now][i]);
			}
			else
				son[now][i] = son[fafail][i];
		}
	}
}

void Query()
{
	int now = 0, len = text.size();
	for(int i = 0; i < len; i++)
	{
		now = son[now][text[i]-'a'];
		for(int j = now; j; j = fail[j])
			if(cnt[j])
				mp[text.substr(i-cnt[j]+1, cnt[j])]++;
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	while(cin >> n)
	{
		if(n == 0)
			break;
		memset(cnt, 0, sizeof cnt);
		memset(son, 0, sizeof son);
		memset(fail, 0, sizeof fail);
		idx = 0;
		mp.clear();
		for(int i = 1; i <= n; i++)
		{
			cin >> query[i];
			insert(i);
		}
		GetFail();
		cin >> text;
		Query();
		int _max = 0;
		for(unordered_map::iterator it = mp.begin(); it != mp.end(); it++)
			_max = max(it->second, _max);
		cout << _max << endl;
		for(int i = 1; i <= n; i++)
			if(mp[query[i]] == _max)
				cout << query[i] << endl;
	}
    return 0;
}