HDU 1251 统计难题【字典树】

题意：中文题--跟着模板敲的--第一棵字典树--@_@
 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>  
 5 using namespace std;
 6 typedef struct node
 7 {
 8     int cnt;
 9     struct node *next[26];
10 } Trie;
11 Trie *create()
12 {
13     Trie *p=(Trie *)(malloc)(sizeof(Trie));
14     p->cnt=1;
15     for(int i=0;i<26;i++) p->next[i]=NULL;
16     return p;
17 }
18 
19 void insert(Trie *p,char *str)
20 {
21     int i=0;
22     while(str[i])
23     {
24         int idx=str[i]-'a';
25         if(p->next[idx]) p->next[idx]->cnt++;
26         else p->next[idx]=create();
27         p=p->next[idx];
28         i++;
29     }
30 }
31 int search(Trie *p,char *str)
32 {
33     int len=strlen(str);
34     for(int i=0;i<len;i++)
35     {
36         int idx=str[i]-'a';
37         p=p->next[idx];
38         if(p==NULL) return 0;
39     }
40     return p->cnt;    
41 }
42 
43 int main()
44 {
45     Trie *p=create();
46     char str[15];
47     while(gets(str)&&str[0])
48     insert(p,str);
49     while(scanf("%s",str)!=EOF)
50     printf("%d
",search(p,str));    
51 }
View Code