*HDU1251 字典树

时间：2022-08-06 15:53:47

统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 35639    Accepted Submission(s): 13322

Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
 
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

 
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
 
Sample Input
banana
band
bee
absolute
acm
 
ba
b
band
abc
 
Sample Output
2
3
1
 
Author
Ignatius.L
 
代码：
 //动态字典树模板

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<malloc.h>

 using namespace std;

 struct Trie

 {

     int v;

     Trie *next[];  //26个小写英文字母，v在这里保存到每个节点有几个单词，根据题意变化

 };

 Trie *root;

 void Tinsert(char s[])

 {

     int len=strlen(s);

     Trie *p=root,*q;

     for(int i=;i<len;i++)

     {

         int id=s[i]-'a';    //换成编号

         if(p->next[id]==NULL)

         {

             q=new Trie;

             for(int j=;j<=;j++)

             q->next[j]=NULL;

             q->v=;

             p->next[id]=q;

         }

         p=p->next[id];

         p->v++;

     }

 }

 int Tsearch(char s[])

 {

     int len=strlen(s);

     Trie *p=root;

     for(int i=;i<len;i++)

     {

         int id=s[i]-'a';

         if(p->next[id]==NULL)

         return ;

         p=p->next[id];

     }

     return p->v;

 }

 void Tdelete(Trie *t)   //动态字典树释放内存

 {

     if(t==NULL)

     return;

     for(int i=;i<;i++)

     if(t->next[i]!=NULL)

     Tdelete(t->next[i]);

     free(t);

 }

 int main()

 {

     char ch[];

     root=new Trie;

     for(int i=;i<;i++)

     root->next[i]=NULL;

     root->v=;

     while(gets(ch)&&ch[])

     Tinsert(ch);

     while(scanf("%s",ch)!=EOF)

     printf("%d\n",Tsearch(ch));

     Tdelete(root);

     return ;

 }
 //仿照上面的动态字典树写的一个静态字典树

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int const MAX=;  //树节点总数

 int const CON=;      //26个小写英文字母

 int nod[MAX][CON],val[MAX];  //节点，节点权值

 int sz;   //记录节点序号

 void init()

 {

     sz=;

     memset(nod[],,sizeof(nod[]));

     val[]=;

 }

 void insert(char s[])

 {

     int len=strlen(s);

     int rt=;

     for(int i=;i<len;i++)

     {

         int id=s[i]-'a';

         if(nod[rt][id]==)

         {

             memset(nod[sz],,sizeof(nod[sz]));

             nod[rt][id]=sz;

             val[sz++]=;

         }

         rt=nod[rt][id];

         val[rt]++;

     }

 }

 int search(char s[])

 {

     int len=strlen(s);

     int rt=;

     for(int i=;i<len;i++)

     {

         int id=s[i]-'a';

         if(nod[rt][id]==)

         return ;

         rt=nod[rt][id];

     }

     return val[rt];

 }

 int main()

 {

     char ch[];

     init();

     while(gets(ch)&&ch[])

     insert(ch);

     while(scanf("%s",ch)!=EOF)

     printf("%d\n",search(ch));

     return ;

 }

相关文章