记录编号	35805	评测结果	AAAAAAAAAA
题目名称	[Youdao2010] 有道搜索框	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.834 s
提交时间	2012-03-03 09:19:12	内存使用	0.38 MiB

#include <fstream>
using namespace std;
ifstream fin("youdao.in");
ofstream fout("youdao.out");
string S[10001],T[10001];
int N,Q,L[10001],OT;
class Node
{
public:
	int AT,Index;
	Node *son[27];
	Node *New()
	{
		Node *newp=new Node;
		newp->AT=0;
		for(int i=1;i<=26;i++)
			newp->son[i]=0;
		return newp;
	}
}Root;
Node *Add(Node *p,char ch)
{
	if(p->son[ch-'a'+1])
		return p->son[ch-'a'+1];
	else
	{
		p->son[ch-'a'+1]=p->New();
		p=p->son[ch-'a'+1];
		return p;
	}
}
void Ins(int pos)
{
int i;
Node *p=&Root;
	for(i=0;i<L[pos];i++)
		p=Add(p,S[pos][i]);
	p->Index=pos;
	p->AT++;
}

void Initialize()
{
int i;
	fin>>N;
	for(i=1;i<=N;i++)
	{
		fin>>S[i];
		L[i]=S[i].length();
		Ins(i);
	}
}
Node *Que(Node *p,char ch)
{
	if(p->son[ch-'a'+1])
		return p->son[ch-'a'+1];
	else
		return 0;
	
}
void Op(Node *p)
{
int i;
	if(p->AT > 0 && OT<8)
	{
		fout<<S[p->Index]<<" ";
		OT++;
	}
	for(i=1;i<=26;i++)
		if(p->son[i])
			Op(p->son[i]);
}
void Search_Op(int pos)
{
int i;
Node *p=&Root;
	for(i=0;i<L[pos];i++)
	{
		p=Que(p,T[pos][i]);
		if(p==0)
			break;
	}
	OT=0;
	if(p==0)
		fout<<T[pos];
	else
		Op(p);
	fout<<endl;
}
void Ans()
{
int i;	
	fin>>Q;
	for(i=1;i<=Q;i++)
	{
		fin>>T[i];
		L[i]=T[i].length();
		Search_Op(i);
	}	
}

int main()
{
	Initialize();
	
	Ans();
	
	fin.close();
	fout.close();
	return 0;
}