记录编号	566817	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.231 s
提交时间	2021-11-16 22:10:58	内存使用	28.90 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 505;
const int SIZE = 26;
char s[15][55];
char t[100000005];
int trie[maxn][SIZE],in[maxn],val[maxn],ans[maxn],Realans[maxn],fail[maxn];
int n,rt,sz;
queue<int> q;
void insert(char* s,int number) {
	int len = strlen(s + 1),u = rt;
	for(int i = 1;i <= len;++ i) {
		int c = s[i] - 'a';
		if(!trie[u][c])trie[u][c] = ++ sz;
		u = trie[u][c];
	}
	val[u] = number;
	return ;
}
void bfs() {
	for(int i = 0;i < SIZE;++ i) {
		if(!trie[rt][i])continue ;
		fail[trie[rt][i]] = rt;
		q.push(trie[rt][i]);
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 0;i < SIZE;++ i) {
			int& v = trie[u][i];
			if(!v) {
				v = trie[fail[u]][i];
				continue ;
			}
			else {     
				fail[v] = trie[fail[u]][i];
				++ in[fail[v]];
				q.push(v);
			}
		}
	}
	return ;
}
void query(char* s) {
	int len = strlen(s + 1),u = rt;
	for(int i = 1;i <= len;++ i) {
		int c = s[i] - 'a';
		u = trie[u][c];
		++ ans[u];
	}
	return ;
}
void TopoSort() {
	for(int i = 0;i <= sz;++ i) {
		if(!in[i])q.push(i);
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		Realans[val[u]] = ans[u];
		ans[fail[u]] += ans[u];
		if(!-- in[fail[u]])q.push(fail[u]);
	}
	return ;
}
int main() {
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	rt = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		scanf("%s",s[i] + 1);
		insert(s[i] , i);
	}
	bfs();
	scanf("%s",t + 1);
	query(t);
	TopoSort();
	for(int i = 1;i <= n;++ i) {
		printf("%s %d\n",s[i] + 1,Realans[i]);
	} 
	fclose(stdin);
	fclose(stdout);
	return 0;
}