题目链接：https://vjudge.net/contest/158125#problem/A
题意：
系统中，strcmp函数是这样执行的，给定 n 个字符串，求两两比较时，strcmp函数要比较多少次？
如：
t h a n t h e r e
t h a t t h e
2 2 2 1 2 2 2 1
直接两两比较是超时的。
可以这样建立一个字典树：
可以发现一直要比较到交叉处，和这个交叉点的深度有关(2*depth+1)。
1、这个字典序每一个交叉点都是要计算的，所以采用邻接表的形式存图；
2、每个结点都要计算他的叶子结点的个数，当分叉的时候，那么说明这里有两个（多个）不同的单词，从中要选择两个单词，计算有多少种搭配，比较次数就是这些搭配*(2*depth+1);
3、递归找下一个结点。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxnode = 4000 * 1000 + 10; 6 const int sigma_size = 26; 7 8 struct Trie 9 { 10 int head[maxnode]; 11 int next[maxnode]; 12 char ch[maxnode]; 13 int tot[maxnode]; 14 int sz; 15 long long ans; 16 void clear() 17 { 18 sz = 1; 19 tot[0] = head[0] = next[0] = 0; 20 } 21 22 void insert(const char *s) 23 { 24 int u = 0, v, n = strlen(s); 25 tot[0]++; 26 for(int i = 0; i <= n; i++) 27 { 28 // 找字符a[i] 29 bool found = false; 30 for(v = head[u]; v != 0; v = next[v]) 31 if(ch[v] == s[i]) // 找到了 32 { 33 found = true; 34 break; 35 } 36 if(!found) 37 { 38 v = sz++; // 新建结点 39 tot[v] = 0; 40 ch[v] = s[i]; 41 next[v] = head[u]; 42 head[u] = v; // 插入到链表的首部 43 head[v] = 0; 44 } 45 u = v; 46 tot[u]++; 47 } 48 } 49 50 51 void dfs(int depth,int u) 52 { 53 if(head[u]==0) //叶子节点 54 ans+=tot[u]*(tot[u]-1)*depth; 55 else 56 { 57 int sum =0; 58 for(int v=head[u]; v!=0; v=next[v]) 59 { 60 sum+=tot[v]*(tot[u]-tot[v]); 61 } 62 ans+=sum/2*(2*depth+1); 63 for(int v=head[u]; v!=0; v=next[v]) 64 dfs(depth+1,v); 65 } 66 } 67 68 long long count() 69 { 70 ans = 0; 71 dfs(0,0); 72 return ans; 73 } 74 75 } trie; 76 77 char word[1010]; 78 79 int main() 80 { 81 int n; 82 int kase = 1; 83 while(scanf("%d",&n),n) 84 { 85 trie.clear(); 86 for(int i=0; i<n; i++) 87 { 88 scanf("%s",word); 89 trie.insert(word); 90 } 91 printf("Case %d: %lld ",kase++,trie.count()); 92 } 93 94 return 0; 95 }