题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2832
题意：模拟strcmp（）函数，给n个字符串，两两之间进行比較，问须要进行多少次比較？
解析：字符串非常多，数据量大。按题意两两比較显然不现实。假设把全部的单词插入到一棵Trie里面会怎么样呢？考虑than和that相应的结点，than和that的前3个字符是一样的，但第4个字符不同。因此比較次数是7。不仅如此，不论什么两个在同一结点处分叉的字符串都须要比較7次。
AC代码：
#include <bits/stdc++.h>
using namespace std; const int maxnode = 4000 * 1000 + 5;
const int sigma_size = 26; struct Trie{ //因为字符集较大，故用左儿子-右兄弟表示法保存
int head[maxnode]; //左儿子编号
int next[maxnode]; //右兄弟编号
char ch[maxnode]; //结点上的字符
int tot[maxnode]; //以该结点为根的结点总数
int sz;
long long ans; void clear(){ sz = 1; tot[0] = head[0] = next[0] = 0; } //初始仅仅有一个根结点 void insert(const char *s){
int u = 0, v, n = strlen(s);
tot[0] ++;
for(int i=0; i<=n; i++){
bool found = false;
for(v=head[u]; v!=0; v=next[v]){
if(ch[v] == s[i]){
found = true;
break;
}
}
if(!found){ //没找到，新建节点
v = sz++;
tot[v] = 0;
ch[v] = s[i];
next[v] = head[u];
head[u] = v; //插到链表首部
head[v] = 0;
}
u = v;
tot[u] ++;
}
} // 统计LCP=u的全部单词两两的比較次数之和
void dfs(int depth, int u) {
if(head[u] == 0) // 叶结点
ans += tot[u] * (tot[u] - 1) * depth;
else {
int sum = 0;
for(int v = head[u]; v != 0; v = next[v])
sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其它子树中再选一个
ans += sum / 2 * (2 * depth + 1); // 每种选法统计了两次。故除2
for(int v = head[u]; v != 0; v = next[v])
dfs(depth+1, v);
}
} // 统计
long long count() {
ans = 0;
dfs(0, 0);
return ans;
} }; Trie T; int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif // sxk int n, t = 0;
char s[1002];
while(scanf("%d", &n) != EOF && n){
T.clear();
for(int i=0; i<n; i++){
scanf("%s", s);
T.insert(s);
}
printf("Case %d: %lld\n", ++t, T.count());
}
return 0;
}