字典树 (sdut 2828)

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

参考了张明同学的代码:
http://blog.csdn.net/sdut_jk17_zhangming/article/details/79168598

模板题,但依然卡了我一晚上的MLE;

需要注意的是结构体里指向孩子的不能用指针,只能用数组,而且必须用静态内存,否则都会MLE;

我的代码:

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    int next[26];//存放孩子的数组下标,用来代替指针以节省空间
};
node a[505000];
int top;
int create_kong()//新建节点
{
    memset(a[top].next,-1,sizeof(a[top].next));//26个孩子都清-1
    a[top++].data=0;
    return top-1;
}
void create(int root,char *str)//建树
{
    int t;
    for(int i=0; str[i];i++)
    {
        t=str[i]-'a';
        if(a[root].next[t]==-1)//若==-1说明之前没存过这个
        {
            a[root].next[t]=create_kong();//需要新建第t个孩子
        }
        root=a[root].next[t];//更新root,继续看下一个字母
    }
    a[root].data++;//单词的结束标志,有了这个标志查询前缀就不会输出yes了
}
int find(int root,char *str)
{
    int i,t;
    for(i=0;str[i];i++)
    {
        t=str[i]-'a';
        if(a[root].next[t]==-1)return 0;//若发现没有对应字母的孩子,返回0,表示无
        root=a[root].next[t];
    }
    return a[root].data;//返回最后一个字母的数组里的值,若为零说明不是单词(为其他单词的前缀)
}
int main()
{
    int n,m,root;
    char str[12];
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
        top=0;
        root=create_kong();//字典树的根节点都是空的,方便向下查找
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            create(root,str);//建树
        }
        for(int i=0;i<m;i++)
        {
            scanf("%s",str);
            if(find(root,str))printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注