字典樹

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

遇到單詞不認識怎么辦?查字典啊，已知字典中有n個單詞，假設單詞都是由小寫字母組成。現有m個不認識的單詞，詢問這m個單詞是否出現在字典中。

Input

含有多組測試用例。

第一行輸入n，m(n>=0&&n<=100000&&m>=0&&m<=100000)分別是字典中存在的n個單詞和要查詢的m個單詞.

緊跟著n行，代表字典中存在的單詞。

然后m行，要查詢的m個單詞

n=0&&m=0程序結束

數據保證所有的單詞都是有小寫字母組成，并且長度不超過10

Output

若存在則輸出Yes，不存在輸出No .

Example Input

3 2

aab

aa

ad

ac

ad

0 0

Example Output

No

Yes

Hint

Author

gyx

SDUTACM

#include <iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<stdlib.h>#include<bits/stdc++.h>using namespace std;struct node{   int cnt;   int next[26];} tree[500005];int a;int creat(){   memset(tree[a].next,0,sizeof(tree[a].next));   tree[a].cnt =0;   return a++;}//用next數組名字本身存字母，數組中的數據存的是下一代節點位置void insert(int top,char *str){   int i,len,t;   for(i=0;str[i];i++)//每增加一個字母相當于多增加了一代   {       t = str[i]-'a';       if(tree[top].next[t]==0)//開辟下一代       {          tree[top].next[t]= creat();       }       top = tree[top].next[t];//存儲完成進入下一代   }   ++tree[top].cnt;//cnt 則存儲以當前字母結束字符串出現次數}int search(int top,char *str){   int i,t;   for(i=0;str[i];i++)   {      t = str[i]-'a';      if(tree[top].next[t]==0)//假如在樹家族中后繼無人，立即截止      {         return 0;      }      top = tree[top].next[t];//進入下一代，看似沖突的相同名字      //實際上占據了不同的空間，相同的建立查找規則使得沖突矛盾消失      //此時才取出字符串出現次數   }   return tree[top].cnt;}int main(){    char str[11];    int n,m,i,top;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0)        {            break;        }        a = 0;        top = creat();        for(i = 0;i< n;i++)        {            scanf("%s",str);            insert(top,str);        }        for(i = 0;i<m;i++)        {            scanf("%s",str);            if(search(top,str)==0)            printf("No/n");            else            printf("Yes/n");        }    }    return 0;}/***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 128msTake Memory: 1004KBSubmit time: 2017-02-10 10:33:19****************************************************/