记录编号 152951 评测结果 AAAAAAAAAA
题目名称 [Youdao2010] 有道搜索框 最终得分 100
用户昵称 Gravatar乌龙猹 是否通过 通过
代码语言 C++ 运行时间 0.067 s
提交时间 2015-03-16 10:37:35 内存使用 0.31 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxc = 27;
struct Trie{
	Trie* ch[Maxc];
	bool end;
	Trie(){
		for(int i=1;i<Maxc;i++) ch[i]=NULL;
		end=0;
	}
};
Trie *T;
char s[80],outs[80];
int n,m,lim,cnt;

void Print(char *a,int l){
	for(int i=0;i<=l;i++) printf("%c",a[i]);
	return;
} 

void Insert(Trie * &o,int now){
	if(now==lim) {o->end=1;return;}
	int pos=s[now]-'a'+1;
	if(o->ch[pos]==NULL)	o->ch[pos]=new Trie;
	Insert(o->ch[pos],now+1);
	return;
}

void Find(Trie *o,int now){
	int pos=s[now]-'a'+1;
	if(cnt==8) return;
	if(now<lim) {
		if(o->ch[pos]==NULL) return;
		outs[now]=pos+'a'-1;
		if(o->ch[pos]->end==1&&now==lim-1){
			cnt++;
			Print(outs,now);
			printf(" ");
		}
		Find(o->ch[pos],now+1);
		return;
	}
	for(int i=1;i<=26&&cnt<8;i++){
		if(o->ch[i]==NULL) continue;
		outs[now]=i+'a'-1;
		if(o->ch[i]->end==1){
			cnt++;
			Print(outs,now);
			printf(" ");
		}
		Find(o->ch[i],now+1);
	}
	return;
}

int main(){
	freopen("youdao.in","r",stdin);
	freopen("youdao.out","w",stdout);
	T=new Trie;
	scanf("%d",&n);
	while(n--) {
		scanf("%s",s);
		lim=strlen(s);
		Insert(T,0);
	}
	scanf("%d",&m);
	while(m--){
		cnt=0;
		scanf("%s",s);
		lim=strlen(s);
		Find(T,0);
		if(cnt==0) Print(s,lim-1);
		printf("\n");
	}
	return 0;
}