HDU1251 字典树板子题

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=26;
 6 struct Trie{
 7     Trie*next[maxn];
 8     int flag;
 9     Trie(){
10         flag=1;
11         memset(next,0,sizeof(next));
12     }
13 }*root;
14 void insert(char*str){
15     int len=strlen(str);
16     Trie*p=root,*q;
17     for(int i=0;i<len;i++){
18         int id=str[i]-'a';
19         if(p->next[id]==NULL){
20             q=new Trie();
21             p->next[id]=q;
22             p=p->next[id];
23         }
24         else {
25             p=p->next[id];
26             (p->flag)++;
27         }
28     }
29 
30 }
31 int query(char*str){
32     int len=strlen(str);
33     Trie*p=root;
34     for(int i=0;i<len;i++){
35         int id=str[i]-'a';
36         p=p->next[id];
37         if(p==NULL)return 0;
38     }
39     return p->flag;
40 }
41 void Free(Trie*T){
42     if(T==NULL)return ;
43     for(int i=0;i<maxn;i++){
44         if(T->next[i])Free(T->next[i]);
45     }
46     delete(T);
47 }
48 
49 int main(){
50     char temp[15];
51     root=new Trie();
52     while(fgets(temp,15,stdin)&&temp[0]!='\n'){
53              temp[strlen(temp)-1]='\0';
54             // cout<<temp<<endl;    
55            insert(temp);
56     }
57     while(~scanf("%s",temp)){
58         printf("%d\n",query(temp));
59     }
60     Free(root);
61     return 0;
62 }