字典树模板

 1 struct Trie
 2 {
 3     const static int maxsig=26;
 4     const static int maxn=500000;
 5     struct node
 6     {
 7         int next[maxsig];
 8         int cnt;
 9     }Trienode[maxn];
10     int size;
11     void init()
12     {
13         memset(Trienode[0].next,0,sizeof(Trienode[0].next));
14         Trienode[0].cnt=0;
15         size=1;
16     }
17     int getid(char c)
18     {
19         return c-'a';
20     }
21     void insert(char *s,int res)
22     {
23         int n=strlen(s);
24         int now=0;
25         for(int i=0; i<n; i++)
26         {
27             int c=getid(s[i]);
28             if(!Trienode[now].next[c])
29             {
30                 memset(Trienode[size].next,0,sizeof(Trienode[size].next));
31                 Trienode[size].cnt=0;
32                 Trienode[now].next[c]=size++;
33             }
34             now=Trienode[now].next[c];
35         }
36         Trienode[now].cnt=res;
37     }
38     int find(char *s)
39     {
40         int now=0,i;
41         int n=strlen(s);
42         for(i=0; i<n; i++)
43         {
44             int c=getid(s[i]);
45             if(Trienode[now].next[c])
46                 now=Trienode[now].next[c];
47             else break;
48         }
49         if(i==n&&Trienode[now].cnt)
50             return Trienode[now].cnt;
51         else return 0;
52     }
53 }tree;