字典树

ゞ浴缸里的玫瑰 2022-08-18 02:28 188阅读 0赞

## 字典树 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

遇到单词不认识怎么办? 查字典啊，已知字典中有n个单词，假设单词都是由小写字母组成。现有m个不认识的单词，询问这m个单词是否出现在字典中。

## 输入 ##

含有多组测试用例。

第一行输入n，m (n>=0&&n<=100000&&m>=0&&m<=100000)分别是字典中存在的n个单词和要查询的m个单词.

紧跟着n行，代表字典中存在的单词。

然后m行，要查询的m个单词

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

数据保证所有的单词都是有小写字母组成，并且长度不超过10

## 输出 ##

若存在则输出Yes，不存在输出No .

## 示例输入 ##

3 2
    aab
    aa
    ad
    ac
    ad
    0 0

## 示例输出 ##

No
    Yes

## 提示 ##

## 来源 ##

gyx

## 示例程序 ##

#include <stdio.h>  
    #include <string.h>  
      
    struct node  
    {  
        int flag;  
        int num;  
        int next[26];  
    }ls[600010];  
      
    int top;  
      
    void creat(char *s,int xb)  
    {  
        int len = strlen(s);  
        for(int i = len - 1;i >= 0;i--)  
        {  
            int zh = s[i] - 'a';  
            if(!ls[xb].next[zh])  
            {  
                ls[top].flag = 0;  
                ls[top].num = 1;  
                for(int j = 0;j < 10;j++)  
                    ls[top].next[j] = 0;  
                ls[xb].next[zh] = top;  
                xb = top++;  
            }  
            else  
            {  
                xb = ls[xb].next[zh];  
                ls[xb].num++;  
            }  
        }  
        ls[xb].flag++;  
    }  
      
    int nfind(char *s,int xb)  
    {  
        int mn = 0x3f3f3f3f;  
        int len = strlen(s);  
        for(int i = len - 1;i >= 0;i--)  
        {  
            int zh = s[i] - 'a';  
            if(ls[xb].next[zh])  
            {  
                xb = ls[xb].next[zh];  
                if(mn > ls[xb].num)  
                    mn = ls[xb].num;  
            }  
            else  
                return -1;  
        }  
        return mn - ls[xb].flag;  
    }  
      
    int main()  
    {  
        int n,m;  
        char s1[10];  
        while(scanf("%d %d",&n,&m)&&(n||m))  
        {  
            top = 0;  
            for(int i = 0;i < 10;i++)  
                ls[top].next[i] = 0;  
            top++;  
            for(int i = 0;i < n;i++)  
            {  
                scanf("%s",s1);  
                creat(s1,0);  
            }  
            //scanf("%d",&m);  
            for(int i = 0;i < m;i++)  
            {  
                scanf("%s",s1);  
                int fh = nfind(s1,0);  
                if(fh == -1)  
                    printf("No\n");  
                else  
                    printf("Yes\n");  
            }  
        }  
        return 0;  
    }