记录编号	221635	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.311 s
提交时间	2016-01-25 10:01:27	内存使用	0.32 MiB

//KZNS
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
//
ifstream fin ("ACautomata.in");
ofstream fout ("ACautomata.out");
//
class Point {
public:
	int nt[26], fail;
	vector<int> tg;
	Point() {
		memset(nt, 0, sizeof(nt));
	}
};
//
int N;
vector<Point> tree;
vector<string> ss;
vector<int> eds;
//
inline int cn(char c) {
	return c-'a';
}
inline void trno() {
	Point u;
	tree.push_back(u);
}
inline void adup(int x) {
	vector<int> &u=tree[x].tg;
	for (int i=0; i<u.size(); i++) {
		eds[u[i]]++;
	}
}
//
void rin() {
	fin >>N;
	string s;
	for (int i=0; i<N; i++) {
		fin >>s;
		ss.push_back(s);
		eds.push_back(0);		
	}
}
void inst(int n, string s) {
	int j=0;
	for (int i=0; i<s.length(); i++) {
		if (tree[j].nt[cn(s[i])]) {
			j=tree[j].nt[cn(s[i])];
		}
		else {
			tree[j].nt[cn(s[i])]=tree.size();
			trno();
			j=tree[j].nt[cn(s[i])];
		}
	}
	tree[j].tg.push_back(n);
}
void mfail() {
	tree[0].fail=-1;
	queue<int> ls;
	ls.push(0);
	int u;
	while (!ls.empty()) {
		u=ls.front();
		ls.pop();
		Point &p=tree[u];
		for (int i=0; i<26; i++) {
			if (p.nt[i]) {
				ls.push(p.nt[i]);
				Point &pc=tree[p.nt[i]];
				int k=p.fail;
				while (true) {
					if (k<0) {
						pc.fail=0;
						break;
					}
					else if (tree[k].nt[i]) {
						pc.fail=tree[k].nt[i];
						Point &pf=tree[pc.fail];
						for (int j=0; j<pf.tg.size(); j++) {
							pc.tg.push_back(pf.tg[j]);
						}
						break;
					}
					else {
						k=tree[k].fail;
					}
				}
			}
		}
	}
}
void ck(string &s) {
	int i=0, j=0;
	while (i<s.length()) {
		if (j<0) {
			i++;
			j++;
		}
		else if (tree[j].nt[cn(s[i])]) {
			j=tree[j].nt[cn(s[i])];
			i++;
			adup(j);
		}
		else {
			j=tree[j].fail;
		}
	}
}
void pot() {
	for (int i=0; i<N; i++) {
		fout <<ss[i] <<' ' <<eds[i] <<endl;
	}
}
//
int main() {
	rin();
	Point pu;
	tree.push_back(pu);
	for (int i=0; i<N; i++) {
		inst(i, ss[i]);
	}
	mfail();
	string s;
	fin >>s;
	ck(s);
	pot();
	return 0;
}
//UBWH