统计难题

Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u

Description

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

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 

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

Output

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

Sample Input

bananabandbeeabsoluteacmbabbandabc

Sample Output

2310 //美名字典树，没见过，自己捣鼓了一下午，超内存了。提交用 G++ 就超内存，C++ 不超。。。然后 wrong anser 原因在于输入， 不知道为什么，如下输入是对的。

1 int main() 2 { 3     char str[30]; 4     while(gets(str)&&str[0]) 5     { 6         build(str); 7     } 8     while(gets(str)) 9     {10         printf("%d\n",querry(str));11     }12     return 0;13 }

而我的，是错的，反正运行起来是没错的。

1 int main() 2 { 3     char xxx; 4     int len; 5     while (xxx=getchar()) 6     { 7         if (xxx=='\n') break; 8         str[0]=xxx; 9         scanf("%s",str+1);10         len=strlen(len);11         build(len);12         xxx=getchar();13     }14     while (scanf("%s",&str)!=EOF)15     {16         len=strlen(str);17         printf("%d\n",find(len));18     }19 return 0;20 }

好了，给AC代码，先给个别人的 124ms

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 using namespace std; 5 struct node 6 { 7     int num; 8     node* next[26]; 9     node()10     {11         num=0;12         memset(next,NULL,sizeof(next));13     }14 };15 node* root=new node();16 node* rt;17 int id,len;18 19 void build(char str[30])20 {21     rt=root;22     len=strlen(str);23     for(int i=0;i
             
              next[id]==NULL)27             rt->next[id]=new node();28         rt=rt->next[id];29         rt->num++;30     }31 }32 33 int querry(char str[30])34 {35     rt=root;36     len=strlen(str);37     for(int i=0;i
              
               next[id]==NULL)41             return 0;42         rt=rt->next[id];43     }44     return rt->num;45 }46 int main()47 {48     char str[30];49     while(gets(str)&&str[0])50     {51         build(str);52     }53     while(gets(str))54     {55         printf("%d\n",querry(str));56     }57     return 0;58 }
              
             
            
           
          

我的，注释比较详细，递归建树的要慢一点 202ms

1 #include 
          
            2 #include 
           
             3 #include 
            
              4  5 struct Node 6 { 7     int flag; 8     struct Node * next[26]; 9     Node()10     {11         flag=0;12         memset(next,NULL,sizeof(next));13     }14 };15 Node * root=new Node();16 char str[15];17 18 struct Node * set(int len,int step,struct Node * k)19 {20     if (step+1==len)    k->flag++;//说明到这是个单词21 22     if (step+1
             
              flag++; //记录自己下面还有几个单词25 26         if (k->next[str[step+1]-'a']==NULL)//如果没有建立过27         {28             k->next[str[step+1]-'a']=new Node();29             k->next[str[step+1]-'a']=set(len,step+1,k->next[str[step+1]-'a']);//继续建设30         }31         else32             set(len,step+1,k->next[str[step+1]-'a']);33     }34     return k;35 }36 37 int find(int len,int step,struct Node * k)38 {39     if (step+1
              
               next[str[step+1]-'a']==NULL)//没有这种单词42             return 0;43 44         return find(len,step+1,k->next[str[step+1]-'a']);45     }46 47     return k->flag;48 }49 50 void Del(Node * k)51 {52     int i;53     for (i=0;i<26;i++)54         if (k->next[i]!=NULL)55             Del(k->next[i]);56     delete k;57 }58 59 int main()60 {61     int len;62     while(gets(str)&&str[0])63     {64         len=strlen(str);65         set(len,-1,root);66     }67     while(gets(str))68     {69         len=strlen(str);70         printf("%d\n",find(len,-1,root));71     }72     Del(root);73     return 0;74 }