codevs 4189辞書【辞書ツリー】

1499 ワード

時間制限:1 s
 空間制限:25000 KB
 マスターマスターマスター
問題を解く
 
Description
一番経て、skyzhongはすごい辞書をもらいました.この辞書にはn個の単語があります.
今skyzhongは辞書であるアルファベットで始まる単語を調べる必要があります.
skyzhongはaを調べたいです.
Aで始まる単語だけでいいです.
skyzhongはこの単語があるかどうかだけを知りたいです.(彼がいないので調べません.)
あるなら、YESを出力してください.もしないなら、NOを出力してください.
 
Input Description
最初の行の一つの数n
2行目からn+1行目までの1行の文字列
次の行の数mはskyzhongで調べたい回数を表します.
m行に続いて、一つの文字列は、skyzhongが調べたいものを表します.
 
Output Description
全部m行です.この文字列があればYESを出力します.でないとNOを出力します.
 
Sample Input
3
asd
asfdghj
asfd
3
asd
asdghj
asf
 
Sample Output
YES
NO
YES
データ範囲とヒント Data Size&Hint
文字列は小文字だけで、しかも長さ≦8
 
タイトルリンク:codevs 4189辞書
辞書ツリーのテンプレートの問題
ACのC言語コード:
#include
#include
#define N 600005
int trie[N][26];
int tot;

void insert(char *s,int rt)
{
	int i;
	for(i=0;s[i];i++){
		int x=s[i]-'a';
		if(!trie[rt][x])
		  trie[rt][x]=++tot;
		rt=trie[rt][x];
	}
}

int find(char *s)
{
	int i,rt=0;
	for(i=0;s[i];i++){
		int x=s[i]-'a';
		if(!trie[rt][x])
		  return 0;
		rt=trie[rt][x];
	}
	return 1;
}

int main()
{
	int n,m;
	char s[20];
	tot=0;
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		insert(s,0);
	}
	scanf("%d",&m);
	while(m--){
		scanf("%s",s);
		if(find(s))
		  printf("YES
"); else printf("NO
"); } return 0; }