当前位置: 代码迷 >> 综合 >> 字典树 oj
  详细解决方案

字典树 oj

热度:21   发布时间:2024-01-14 23:01:38.0

字典树

Time Limit: 1000MS Memory Limit: 65536KB
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
静态分配内存,数组模拟
#include <stdio.h>
#include <string.h>
struct node
{
    int isend; //是否结束
    int next[26];
}L[5050000]; //静态分配内存
int top,n,m;
char a[20],b[20];
int creat() //创建新结点
{
    memset(L[top].next,-1,sizeof(L[top].next));
    L[top].isend = 0;
    return top++;
}
int xiab(char c) // 求下标
{
    return c - 'a';
}
void insert(int root,char *s) //插入
{
    int i,len = strlen(s);
    for(i = 0;i < len;i++)
    {
        if(L[root].next[xiab(s[i])] == -1)
        {
            L[root].next[xiab(s[i])] = creat();
        }
        root = L[root].next[xiab(s[i])];
    }
    L[root].isend = 1;
}
int search(int root,char *s)//查找
{
    for(int i =0;s[i]!='\0';i++)
    {
        if(L[root].next[xiab(s[i])] == -1)
            return 0;
        root = L[root].next[xiab(s[i])];
    }
    return L[root].isend;
}
int main()
{
    int i,j,root;
    while(scanf("%d%d",&n,&m) != EOF&&(n||m))
    {
        top = 0;
        root = creat();
        for(i = 0;i < n;i++)
        {
            scanf("%s",a);
            insert(root,a);
        }
        for(i = 0;i <m;i++)
        {
            scanf("%s",b);
            printf("%s\n",search(root,b)?"Yes":"No");
        }
    }
    return 0;
}

另一种做法,MLE不知为什么
#include <stdio.h>
#include <string.h>char str[20];
struct node *L;
struct node
{int isend;  //0非最后一个节点,1最后一个节点struct node *next[26]; //按字母编号
};
void insert(char str[]) //插入
{int len = strlen(str);if(len == 0)return ;int i;struct node *q = L;for(i = 0;i < len;i++){int no = str[i] - 'a';if(q->next[no] == NULL) //不存在该前缀{struct node *p;p = (struct node *)malloc(sizeof(struct node));chushihua(p);q->next[no] = p;q = p;}else //存在{q = q->next[no];}}q->isend = 1; //最后一个节点,
}
void chushihua(struct node *p)  //初始化
{p->isend = 0;for(int i = 0;i < 26;i++){p->next[i] = NULL;}
}
void find(char str[]) //查找
{int len = strlen(str);if(str == 0)printf("No\n");int i;struct node *p = L;for(i = 0;i < len;i++){int no = str[i] - 'a';if(p->next[no] != NULL){p = p->next[no];}else{printf("No\n");return ;}}if(p->isend == 1)printf("Yes\n");elseprintf("No\n");
}
void end(struct node *p)
{int i;for(i = 0;i < 26;i++){if(p->next[i] != NULL)end(p->next[i]);}free(p);
}
int main()
{int n,m,i,j;while(scanf("%d%d",&n,&m) != EOF&&(n||m)){L = (struct node *)malloc(sizeof(struct node));chushihua(L);for(i = 0;i < n;i++){scanf("%s",str);insert(str);}for(i = 0;i < m;i++){scanf("%s",str);find(str);}end(L);}return 0;
}

  相关解决方案