记录编号	311617	评测结果	AAAAAAAAAA
题目名称	[Youdao2010] 有道搜索框	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2016-09-24 20:23:10	内存使用	101.28 MiB

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iomanip>
#include<functional>
#include<queue>
#include<stack>
#include<map>
#define WJ(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
#define JW fclose(stdin);fclose(stdout);
using namespace std;
const int maxnode=1000000;
const int sigma_size=26;
struct Trie{
	int ch[maxnode][sigma_size],sz,tot;
	string st;
	bool val[maxnode];
	Trie(){
		sz=1;
		val[sz]=0;
		memset(ch[1],0,sizeof(ch[1]));
	}
	inline int idx(const char& c){
		if(c>='A'&&c<='Z')return c-'A';
		else return c-'a';
	}
	void insert(char *s/*,int v*/){
		int u=0;
		for(int i=0;s[i];++i){
			int c=idx(s[i]);
			if(!ch[u][c]){
				sz++;
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz]=0;
				ch[u][c]=sz;
			}
			u=ch[u][c];
		}
		val[u]=1;
	}
	inline bool query(char *s){
		int u=0;
		for(int i=0;s[i];++i){
			int c=idx(s[i]);
			if(!ch[u][c])return 0;
			u=ch[u][c];
		}
		return val[u];
	}
	inline void dfs(const string& s,const int& u){
		if(tot==8)return;
		if(val[u])tot++,cout<<s<<' ';
		for(int i=0;i<26;i++)
			if(ch[u][i])dfs(s+char(i+'a'),ch[u][i]);
	}
	inline bool find(char *s){
		tot=0;st="";
		int u=0;
		for(int i=0;s[i];++i){
			int c=idx(s[i]);
			if(!ch[u][c])return 0;
			st+=s[i];
			u=ch[u][c];
		}
		dfs(st,u);
		return tot;
	}
};
Trie a;
int main(){
	#define submit
	#ifdef submit
	WJ(youdao);
	#endif
	char str[maxnode];int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		a.insert(str);
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		if(!a.find(str))printf("%s\n",str);
		else putchar(10);
	}
	JW;
	return 0;
}