统计难题

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

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana

band

bee

absolute

acm

band

abc

Sample Output

Author

Ignatius.L

Recommend

Ignatius.L

字典树.....

代码：

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 typedef struct trie

 {

     //由于只有小写字母a~z-->26

     struct trie *child[];

     int deep;  //--->相似的程度

 }Trie;

 /*作为一个头指针*/

 Trie *root;

 void Insert(char *a)

 {

     int len,i;

     Trie *current, *creatnew;

     len=strlen(a);

     if(len)

     {

              current=root;

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

         {

           if(current->child[a[i]-'a']!=)

           {

              current=current->child[a[i]-'a'];

              current->deep=current->deep+;

           }

           else

           {

               creatnew=(Trie *)malloc(sizeof(Trie));

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

              {

                 creatnew->child[j]=;

              }

               current->child[a[i]-'a']=creatnew;

               current=creatnew;

               current->deep=;

           }

         }

     }

 }

 int Triefind(char *a)

 {

    int i,len;

    Trie *current;

    len=strlen(a);

    if(!len) return ;

    current=root;

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

    {

        if(current->child[a[i]-'a']!=)

        {

          current=current->child[a[i]-'a'];

        }

        else

             return ;

    }

     return current->deep;

 }

 int main()

 {

     int i;

     char temp[];

     root=(Trie *)malloc(sizeof(Trie));

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

     {

         root->child[i]=;

     }

     root->deep=;

     while(gets(temp),strcmp(temp,""))

         Insert(temp);

      memset(temp,'\0',sizeof(temp));

     while(~scanf("%s",temp))

       printf("%d\n",Triefind(temp));

    free(root);

     return ;

 }

模板：

代码:

 /*hdu 1251 字典树之统计*/

 #define LOCAL

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 typedef struct Trie

 {

  struct Trie *child[];

  int deep;

 }trie;

 int idx(char s){

     return s-'a';

 }

 void Insert(char *s,trie *root)

 {

    trie *cur,*newcur;

     cur=root;

     int i,j;

    for(i=;s[i]!='\0';i++)

    {

       if(cur->child[idx(s[i])]==NULL)  //为空指针

       {

          newcur=(trie *)malloc(sizeof(trie));

          newcur->deep=;

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

            newcur->child[j]=NULL; //设置为空指针

           cur->child[idx(s[i])]=newcur;

       }

       cur=cur->child[idx(s[i])];  //向下推一层

       cur->deep+=;   //层数加一

    }

 }

 int query(char *s,trie *root)

 {

     trie *cur=root;

     int i;

     for(i=;s[i]!='\0';i++){

         if(cur->child[idx(s[i])]!=NULL)

             cur=cur->child[idx(s[i])];

         else

             return ;

     }

     int tem=cur->deep;

     return tem;

 }

 void del(trie *root)

 {

     int i=;

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

      if(root->child[i]!=NULL)

        del(root->child[i]);

     }

    free(root);

 }

 char ss[];

 int main()

 {

 #ifdef LOCAL

   freopen("test.in","r",stdin);

 #endif

   trie *root=(trie *)malloc(sizeof(trie));

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

     root->child[i]=NULL;  //设置为空指针

    while(gets(ss),strcmp(ss,""))

     Insert(ss,root);

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

      printf("%d\n",query(ss,root));

      del(root);

  return ;

 }

巴特西

HDUOJ-----（1251）统计难题

统计难题

最新文章

热门文章