UVa 11732 (Tire树) "strcmp()" Anyone?

这道题也是卡了挺久的。

给出一个字符串比较的算法，有n个字符串两两比较一次，问一共会有多少次比较。

因为节点会很多，所以Tire树采用了左儿子右兄弟的表示法来节省空间。

假设两个不相等的字符串的最长公共前缀的长度为i，那么比较次数应该是2i+1。

如果两个字符串相等，比较次数则是2i+2.

可以像大白书上一样先构建好Tire树，然后DFS统计答案。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxnode = 4000 * 1000 + 10;
 5 
 6 struct Tire
 7 {
 8     int sz;
 9     int son[maxnode], bro[maxnode], tot[maxnode];
10     char ch[maxnode];
11     long long ans;
12     void clear() { sz = 1; son[0] = bro[0] = tot[0] = 0; }
13 
14     void insert(char* s)
15     {
16         int u = 0, v, n = strlen(s);
17         tot[0]++;
18         for(int i = 0; i <= n; i++)
19         {
20             bool found = false;
21             for(v = son[u]; v; v = bro[v])
22                 if(ch[v] == s[i]) { found = true; break; }
23             if(!found)
24             {
25                 v = sz++;
26                 son[v] = 0;
27                 bro[v] = son[u];
28                 son[u] = v;
29                 tot[v] = 0;
30                 ch[v] = s[i];
31             }
32             u = v;
33             tot[u]++;
34         }
35     }
36 
37     void dfs(int d, int u)
38     {
39         if(son[u] == 0) { ans += tot[u] * (tot[u]-1) * d; return; }//叶节点
40         long long sum = 0;
41         for(int v = son[u]; v; v = bro[v])
42             sum += tot[v] * (tot[u] - tot[v]);
43         ans += sum / 2 * (d * 2 + 1);
44         for(int v = son[u]; v; v = bro[v]) dfs(d+1, v);
45     }
46 
47     long long count()
48     {
49         ans = 0;
50         dfs(0, 0);
51         return ans;
52     }
53 }tire;
54 
55 const int maxl = 1000 + 10;
56 char s[maxl];
57 
58 int main()
59 {
60     //freopen("in.txt", "r", stdin);
61 
62     int n, kase = 0;
63     while(scanf("%d", &n) == 1 && n)
64     {
65         tire.clear();
66         for(int i = 0; i < n; i++) { scanf("%s", s); tire.insert(s); }
67         printf("Case %d: %lld
", ++kase, tire.count());
68     }
69 
70     return 0;
71 }

代码君

也可以边插入字符串边统计，代码更短，而且速度也更快。这种做法是从某位菊苣的博客中看到的。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxnode = 1000 * 4000 + 10;
 5 
 6 long long ans;
 7 
 8 struct Tire
 9 {
10     int son[maxnode], bro[maxnode], tot[maxnode];
11     char ch[maxnode];
12     int sz;
13     void clear() { sz = 1; son[0] = bro[0] = tot[0] = 0; }
14 
15     void insert(char* s)
16     {
17         int u = 0, v, n = strlen(s);
18         tot[0]++;
19         for(int i = 0; i <= n; i++)
20         {
21             bool found = false;
22             for(v = son[u]; v; v = bro[v])
23                 if(ch[v] == s[i]) { found = true; break; }
24             if(!found)
25             {
26                 v = sz++;
27                 son[v] = 0;
28                 bro[v] = son[u];
29                 son[u] = v;
30                 tot[v] = 0;
31                 ch[v] = s[i];
32             }
33             ans += (tot[u] - 1 - tot[v]) * (2 * i + 1);
34             if(i == n) ans += tot[v] * (2 * i + 2);
35             u = v;
36             tot[u]++;
37         }
38     }
39 }tire;
40 
41 const int maxl = 1000 + 10;
42 char s[maxl];
43 
44 int main()
45 {
46     //freopen("in.txt", "r", stdin);
47 
48     int n, kase = 0;
49     while(scanf("%d", &n) == 1 && n)
50     {
51         tire.clear();
52         ans = 0;
53         for(int i = 0; i < n; i++) { scanf("%s", s); tire.insert(s); }
54         printf("Case %d: %lld
", ++kase, ans);
55     }
56 
57     return 0;
58 }

代码君