字典树

不念不忘少年蓝@ 2022-07-12 05:51 163阅读 0赞

#### 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

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define maxc 26
    #define maxn 1000000
    typedef struct node
    {
        int cnt;
        struct node * next[maxc];
    }trietree;
    
    trietree trie[maxn];
    int top;
    
    trietree * create ()
    {
        int i;
        trietree * t=&trie[top++];
        t->cnt=0;
        for(i=0;i<maxc;i++)
        {
            t->next[i]=NULL;
        }
        return t;
    }
    
    trietree * init()
    {
        top=0;
        return (create());
    }
    
    void insert(trietree * tree,char str[])
    {
        int i,id;
        trietree * p=tree;
        for(i=0;str[i];i++)
        {
            id=str[i]-'a';
            if(!p->next[id])
            {
                p->next[id]=create();
            }
            p=p->next[id];
        }
        p->cnt++;
    }
    
    int find (trietree * tree, char str[])
    {
        int i,id;
        trietree * p=tree;
        for(i=0;str[i];i++)
        {
            id=str[i]-'a';
            if(!p->next[id])
            {
                return 0;
            }
            p=p->next[id];
        }
        return 1;
    }
    int main()
    {
        int n,m,flag;
        char str[16];
        trietree * tree;
        while(scanf("%d%d",&n,&m),n||m)
        {
            tree=init();
            while(n--)
            {
                scanf("%s",str);
                insert(tree,str);
            }
            while(m--)
            {
                flag=0;
                scanf("%s",str);
                flag=find(tree,str);
                if(flag)
                {
                    printf("Yes\n");
                }
                else
                {
                    printf("No\n");
                }
            }
        }
        return 0;
    }