记录编号	155178	评测结果	AAAAAAT
题目名称	AC自动机	最终得分	85
用户昵称	wolf.	是否通过	未通过
代码语言	C++	运行时间	1.084 s
提交时间	2015-03-26 23:41:51	内存使用	0.32 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="\t";
ofstream nnew("ACautomata.in",ios::app);
ifstream fin("ACautomata.in");
#define fout cout
#define Endl endl
#else
ifstream fin("ACautomata.in");
ofstream fout("ACautomata.out");
#endif
class node{
public:
	int n;
	int back;
	int flag;
	vector<int> stroage;
	node(){
		stroage.resize(26,0);
		n=0;
		flag=0;
		back=0;
	}
	void insert(int n,int index){
		stroage[n]=index;
	}
	int find(int n){
		return stroage[n];
	}
};
class point{
public:
	string txt;
	int ans;
	point(string a){
		txt=a;
		ans=0;
	}
	point(){
	}
};
vector<node> TT;
vector<point> ans;
void insert(string txt){
	int r=0;
	for(int i=0;i!=txt.size();++i){
		int t=TT[r].find(txt[i]-'a');
		if(t==0){
			TT.push_back(node());
			TT[r].insert(txt[i]-'a',TT.size()-1);
			r=TT.size()-1;
			TT[r].n=txt[i]-'a';
		}else{
			r=t;
		}
	}
	TT[r].flag=ans.size()-1;
}
void build(){
	TT[0].back=0;
	deque<int> Q;
	for(int i=0;i!=26;++i){
		int r=TT[0].find(i);
		if(r!=0){
			TT[r].back=0;
			Q.push_back(r);
		}
	}
	while(!Q.empty()){
		int pp=Q.front();
		Q.pop_front();
		//cout<<pp<<kk<<char(TT[pp].n+'a')<<kk<<TT[pp].back<<kk<<TT[pp].flag<<endl;
		////////////////////
		for(int i=0;i!=26;++i){
			int nex=TT[pp].find(i);
			if(nex!=0){
				Q.push_back(nex);
				int it=pp,r=TT[TT[it].back].find(TT[nex].n);
				while(r==0&&it!=0){
					it=TT[it].back;
					r=TT[TT[it].back].find(TT[nex].n);
				}
				TT[nex].back=r;
			}
		}
	}
}
void _plus(int i){
	while(i!=0){
		if(TT[i].flag!=0){
			ans[TT[i].flag].ans++;
		}
		i=TT[i].back;
	}
}
void core(string &txt){
	int it=0;
	for(int i=0;i!=txt.size();++i){
		int r=TT[it].find(txt[i]-'a');
		while(r==0&&it!=0){
			it=TT[it].back;
			r=TT[it].find(txt[i]-'a');
		}
		if(r==0){
			it=0;
			continue;
		}
		it=r;
		_plus(it);
	}
	return;
}
int main(){
	int n;
	fin>>n;
	TT.push_back(node());
	TT[0].n=0;
	ans.push_back(point("$"));
	for(int i=0;i!=n;++i){
		string txt;
		fin>>txt;
		ans.push_back(point(txt));
		insert(txt);
	}
	build();
	/*cout<<"下标"<<kk<<"字符"<<kk<<"回溯"<<kk<<"标志标量"<<endl;
	for(int i=0;i!=TT.size();++i){
		cout<<i<<kk<<char(TT[i].n+'a')<<kk<<TT[i].back<<kk<<TT[i].flag<<endl;
	}*/
	string txt;
	fin>>txt;
	core(txt);
	for(int i=1;i!=ans.size();++i){
		fout<<ans[i].txt<<"  "<<ans[i].ans<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Wed Mar 25 2015