记录编号 |
152951 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[Youdao2010] 有道搜索框 |
最终得分 |
100 |
用户昵称 |
乌龙猹 |
是否通过 |
通过 |
代码语言 |
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;
}