记录编号	237453	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.343 s
提交时间	2016-03-17 15:34:55	内存使用	1.54 MiB

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#define maxnode 11000
#define sigma 27
using namespace std;
int count[maxnode];
int ans=0;
struct trie{
	int ch[maxnode][sigma],val[maxnode];
	int f[maxnode],last[maxnode];
	int sv;
	void clear(){
		memset(ch[0],0,sizeof(ch[0]));
		memset(val,0,sizeof(val));
		memset(f,0,sizeof(f));
		memset(last,0,sizeof(last));
		sv=1;
	}
	int idx(char a){
		return a-'a';
	}
	void _insert(const string &s,int v){
		int n=s.size(),u=0;
		for(int i=0;i<n;i++){
            int k=idx(s[i]);
			if(!ch[u][k]){
				memset(ch[sv],0,sizeof(ch[sv]));
				ch[u][k]=sv++;
			}
			u=ch[u][k];
		}
			val[u]=v;
		}
		
	
	void get_fail(){
		queue<int>que;
		for(int i=0;i<sigma;i++){
			int u=ch[0][i];
			if(!u)
			continue;
			que.push(u);
		}
		while(!que.empty()){
			int k=que.front();
			que.pop();
			for(int i=0;i<sigma;i++){
				int u=ch[k][i];
				if(!u)
				continue;
				que.push(u);
				int v=f[k];
				while(v&&!ch[v][i]) v=f[v];
				f[u]=ch[v][i];
				last[u]=val[f[u]]?f[u]:last[f[u]];
			}
		}
	}
	void _find(int j){
		if(j){
			count[val[j]]++;
			_find(last[j]);
		}
	}
	void _find(const string &s){
		int n=s.size(),u=0;
		for(int i=0;i<n;i++){
			int c=idx(s[i]);
			while(u&&!ch[u][c]) u=f[u];
			u=ch[u][c];
			if(val[u]){
				_find(u);
			}
			else if(val[last[u]]){
				_find(last[u]);
			}
		}
	}
};
string hahaha[maxnode];
int main(){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
ios::sync_with_stdio(false);
trie G;
G.clear();
memset(count,0,sizeof(count));
int n;
cin>>n;
for(int j=0;j<n;j++){
	string s;
	cin>>s;
	hahaha[j+1]=s;
	G._insert(s,j+1);
}
string s;
cin>>s;
G.get_fail();
G._find(s);
for(int i=1;i<=n;i++){
	cout<<hahaha[i]<<" "<<count[i]<<endl;
}
}