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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct Trie{
	bool flag;
	int v;
	Trie *nex[26];
};
Trie *root;
char str[501];
char ans[100];
int sum=0;
Trie *New_Trie(){
	Trie *temp=new Trie;
	temp->v=1;
	for (int i=0;i<26;i++)
		temp->nex[i]=NULL;
	return temp;
}
void build(char *str){
	int len=strlen(str);
	Trie *p=root;
	for (int i=0;i<len;++i){
		int id=str[i]-'a';
		if (p->nex[id]==NULL){
			//ans++;
			Trie *q=New_Trie();
			p->nex[id]=q;
			p=p->nex[id];
		}else{
			p->nex[id]->v++;
			p=p->nex[id];
		}
	}
	//p->v=-1;
}
Trie *findTrie(char *str){
	int len=strlen(str);
	Trie *p=root;
	Trie *q=NULL;
	for (int i=0;i<len;++i){
		int id=str[i]-'a';
		q=p;
		p=p->nex[id];
		if (p==NULL) return NULL;
	}
	return p;
}
void dfs_print(Trie *pos,int o){
	Trie *p=pos;
	if (p==NULL){
		int len=strlen(str);
		for (int j=0;j<len;j++)
				printf("%c",str[j]);
		return ;
	}
	int ss=0;
	for (int i=0;i<26;i++)
		if (p->nex[i]!=NULL)
		ss+=p->nex[i]->v;
	if (ss<p->v){
	//	for (int i=1;i<=p->v-ss;i++){
			int len=strlen(str);
			sum++;
			for (int j=0;j<len;j++)
				printf("%c",str[j]);
			for (int j=1;j<o;j++)
				printf("%c",ans[j]);
			printf(" ");
			
		}
			
	//}
	//bool flag=true;
	for (int i=0;i<26;i++){
		if (sum==8) return ;
		ans[o]=i+'a';
		if (p->nex[i]==NULL);
		else{
			//flag=true;
			dfs_print(p->nex[i],o+1);
		}
		
	}
	/*if (!flag){
			int len=strlen(str);
			sum++;
			for (int j=0;j<len;j++)
				printf("%c",str[j]);
			for (int j=1;j<o;j++)
				printf("%c",ans[j]);
			printf(" ");
			if (sum==8) return ;
		}*/
}
void init_work(){
	freopen("youdao.in","r",stdin);
	freopen("youdao.out","w",stdout);
	int n,m;
	scanf("%d\n",&n);
	root=New_Trie();
	for (int i=1;i<=n;i++){
		memset(str,'\0',sizeof(str));
		scanf("%s\n",&str);
		build(str);
	}
	scanf("%d\n",&m);
	Trie *pos;
	for (int i=1;i<=m;i++){
		sum=0;
		memset(str,'\0',sizeof(str));
		memset(ans,'\0',sizeof(ans));
		scanf("%s\n",&str);
		pos=New_Trie();
		pos=findTrie(str);
		dfs_print(pos,1);
		printf("\n");
	}
}
int main(){
	init_work();
	return 0;
}