3道入门字典树例题，以及模板【HDU1251/HDU1305/HDU1671】

HDU1251：http://acm.hdu.edu.cn/showproblem.php?pid=1251

题目大意：求得以该字符串为前缀的数目，注意输入格式就行了。

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 char str[20];
 5 int trie[100000 * 4][30], cnt;
 6 int sum[100000 * 4];
 7 
 8 void insert()
 9 {
10     int len = strlen(str);
11     int rt = 0;
12     for(int i = 0; i < len; i ++)
13     {
14         int id = str[i] - 'a';
15         if(!trie[rt][id])
16             trie[rt][id] = ++ cnt;
17         rt = trie[rt][id];
18         sum[rt] ++;
19     }
20 }
21 
22 int serach()
23 {
24     int len = strlen(str);
25     int rt = 0;
26     for(int i = 0; i < len; i ++)
27     {
28         int id = str[i] - 'a';
29         if(!trie[rt][id])
30             return 0;
31         rt = trie[rt][id];
32     }
33     return sum[rt];
34 }
35 
36 int main()
37 {
38     while(gets(str))
39     {
40         if(strlen(str) == 0)
41             break;
42         insert();
43     }
44     while(scanf("%s", str) != EOF)
45     {
46         printf("%d
", serach());
47     }
48     return 0;
49 }

HDU1251

HDU1305：http://acm.hdu.edu.cn/showproblem.php?pid=1305

题目大意：字符串之间互相不为前缀，则输出YES 否则NO

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 
 5 int trie[40000][3], tot, k_rt[40000], cnt, sum[40000];
 6 char str[15];
 7 
 8 void insert()
 9 {
10     int len = strlen(str);
11     int root = 0;
12     for(int i = 0; i < len; i ++)
13     {
14         int id = str[i] - '0';
15         if(!trie[root][id])
16             trie[root][id] = ++ tot;
17         root = trie[root][id];
18         sum[root] ++;
19     }
20     k_rt[++ cnt] = root; //记录每个01字符串结束的位置 
21 }
22 
23 void init()
24 {
25     mem(trie, 0);
26     mem(k_rt, 0);
27     mem(sum, 0);
28     cnt = 0, tot = 0;
29 }
30 
31 int main()
32 {
33     int k = 1, flag;
34     while(scanf("%s", str) != EOF)
35     {
36         if(str[0] != '9')
37             insert();
38         else
39         {
40             flag = 0;
41             for(int i = 1; i <= cnt; i ++)
42             {
43                 if(sum[k_rt[i]] >= 2)
44                 {
45                     flag = 1;
46                     break;
47                 }
48             }
49             if(flag)
50                 printf("Set %d is not immediately decodable
", k ++);
51             else
52                 printf("Set %d is immediately decodable
", k ++);
53             init();
54         }
55     }
56     return 0;
57 }

HDU1305

HDU1671：http://acm.hdu.edu.cn/showproblem.php?pid=1671

题目大意：与HDU1251是一样的

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 
 5 char str[15];
 6 int trie[100010][12], tot, cnt, k_rt[100010], sum[100010];
 7 
 8 void insert()
 9 {
10     int len = strlen(str);
11     int root = 0;
12     for(int i = 0; i < len; i ++)
13     {
14         int id = str[i] - '0';
15         if(!trie[root][id])
16             trie[root][id] = ++ tot;
17         root = trie[root][id];
18         sum[root] ++;
19     }
20     k_rt[++ cnt] = root; //记录每个字符串的结束位置 ，通过结束位置上的出现次数判断是否是其他字符串的前缀 
21 }
22 
23 void init()
24 {
25     mem(trie, 0);
26     mem(sum, 0);
27     mem(k_rt, 0);
28     tot = 0, cnt = 0;
29 }
30 
31 int main()
32 {
33     int T, n, flag;
34     scanf("%d", &T);
35     while(T --)
36     {
37         init();
38         flag = 0;
39         scanf("%d", &n);
40         getchar();
41         for(int i = 1; i <= n; i ++)
42         {
43             scanf("%s", str);
44             insert();
45         }
46         for(int i = 1; i <= cnt; i ++)
47         {
48             if(sum[k_rt[i]] >= 2)
49             {
50                 flag = 1;
51                 break;
52             }
53         }
54         if(flag)
55             printf("NO
");
56         else
57             printf("YES
");
58     }
59     return 0;
60 }

HDU1671

模板

字典树建树模板：

 1 //建trie树 
 2 void insert()
 3 {
 4     int len = strlen(str);
 5     int root = 0;
 6     for(int i = 0; i < len; i ++)
 7     {
 8         int id = str[i] - '0';
 9         if(!trie[root][id])
10             trie[root][id] = ++ tot;
11         root = trie[root][id];
12         sum[root] ++; //记录数目则需要 
13     }
14     pos[++ cnt] = root; //记录每个字符串的结束位置 ，通
15     //                    过结束位置上的出现次数判断是否是其他字符串的前缀 
16 }   //                     若根据输入判断，则不需要这句话，查找输入的字符串最后一个位置的出现次数即可

建trie树

字典树查找模板：

 1 //trie树查找 
 2 int serach()//bool serach() , 该字符串为前缀的数目/是否存在以该字符串为前缀的字符串 
 3 {
 4     int len = strlen(str);
 5     int rt = 0;
 6     for(int i = 0; i < len; i ++)
 7     {
 8         int id = str[i] - 'a';
 9         if(!trie[rt][id])
10             return 0;//return false;
11         rt = trie[rt][id];
12     }//达到字符串最后一个字符所在位置 
13     return sum[rt]; // return true;
14 }

字典树查找