字典树
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>
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;
}