字典树模板

字典树

这一个比较简单现在回顾也挺简单

直接给出模板有什么不会的直接去模板里理解

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 500005;
 7 int tire[maxn][26];
 8 int flag[maxn];
 9 int tot;
10 
11 void init() {
12     memset(tire, 0, sizeof(tire));
13     memset(flag, 0, sizeof(flag));
14     tot = 1;
15 }
16 
17 void add(char *s, int rt) {
18     for(int i = 0; s[i]; i++) {
19         int x = s[i] - '0';
20         if(tire[rt][x] == 0) {
21             tire[rt][x] = tot++;
22         }
23         rt = tire[rt][x];
24         flag[rt]++;//计算以当前字符串做前缀的字符串的数目
25     }
26 }
27 
28 int cal(char *s, int rt) {
29     for(int i = 0; s[i]; i++) {
30         int x = s[i] - '0';
31         if(tire[rt][x] == 0) {
32             return 0;
33         }
34         rt = tire[rt][x];
35     }
36     return flag[rt];
37 }
38 
39 char s[15];
40 int main() {
41     init();
42     while(gets(s)) {
43         if(strlen(s) == 0) {
44             break;
45         }
46         add(s, 0);
47     }
48     while(EOF != scanf("%s",s)) {
49         printf("%d
",cal(s, 0));
50     }
51 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 struct Node {
 7     Node *next[26];
 8     int cnt;
 9     Node() {
10         for(int i = 0; i < 26; i++) {
11             next[i] = NULL;
12         }
13         cnt = 0;
14     }
15 }root;
16 
17 void add(char *s) {
18     Node *p = &root;
19     for(int i = 0; s[i]; i++) {
20         if(p -> next[s[i] - 'a'] == NULL) {
21             p -> next[s[i] - 'a'] = new Node();
22         }
23         p = p -> next[s[i] - 'a'];
24         p -> cnt++;
25     }
26 }
27 
28 int cal(char *s) {
29     Node *p = &root;
30     for(int i = 0; s[i]; i++) {
31         if(p -> next[s[i] - 'a'] == NULL) {
32             return 0;
33         }
34         p = p -> next[s[i] - 'a'];
35     }
36     return p -> cnt;
37 }
38 
39 void Free(Node *p) {
40     for(int i = 0; i < 26; i++) {
41         if(p -> next[i] != NULL) {
42             Free(p -> next[i]);
43         }
44     }
45     free(p);
46 }
47 
48 char s[15];
49 int main() {
50     while(gets(s)) {
51         if(strlen(s) == 0) {
52             break;
53         }
54         add(s);
55     }
56     while(EOF != scanf("%s",s)) {
57         printf("%d
",cal(s));
58     }
59     Node *p = &root;
60 //    free(p);
61 }

View Code