hdu--1251--字典树

赤裸裸的字典树...就来熟悉下字典树的顺便注意下写的时候的各种小细节

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int size = 26;
 6 char str[size];
 7 typedef struct trie
 8 {
 9     trie* next[size];
10     int cnt;
11 };
12 trie* root;
13 
14 void init()
15 {
16     root = new trie;
17     for( int i = 0 ; i<size ; i++ )
18         root->next[i] = NULL;
19 }
20 
21 void create( char* str )
22 {
23     int len = strlen(str);
24     trie* p = root;
25     //trie* q;
26     for( int i = 0 ; i<len ; i++ )
27     {
28         int id = str[i] - 'a';
29         if( p->next[id] == NULL )
30         {
31             //q = new trie;
32             p->next[id] = new trie;
33             p->next[id]->cnt = 1;
34             for( int j = 0 ; j<size ; j++ )
35             {
36                 p->next[id]->next[j] = NULL;
37             }
38             //p->next[id] = q;
39         }
40         else
41         {
42             p->next[id]->cnt ++;
43         }
44         p = p->next[id];
45     }
46 }
47 
48 int find( char* str )
49 {
50     int len = strlen(str);
51     trie* p = root;
52     for( int i = 0 ; i<len ; i++ )
53     {
54         int id = str[i] - 'a';
55         p = p->next[id];
56         if( p==NULL )
57         {
58             return 0;
59         }
60     }
61     return p->cnt;
62 }
63 
64 int main()
65 {
66     init();
67     while( gets(str) && str[0]!='' )
68     {
69         create( str );
70     }
71     while( cin >> str )
72     {
73         cout << find(str) << endl;
74     }
75     return 0;
76 }

View Code

注释的也是正确的... 当时写着来验证自己想法的=-=

today:

　　if you can't fly then run

　　if you can't run then walk

　　if you can't walk then crawl

　　but wharever you do you have to keep moving forward

just follow your heart