题意：询问所有字符串的比较次数和(注意for循环内的比较也算)
分析：将所有字符串插入到字典树上，然后结点信息记录有几个字符串，那么每走到一个结点就能知道比较到此时需要的次数。学习到链表存结点
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e3 + 5;
const int M = 1e3 + 5;
const int NODE = N * M;
struct Trie {
int head[NODE], nex[NODE];
char ch[NODE];
int cnt[NODE];
int sz;
void clear() {
sz = 1; cnt[0] = head[0] = nex[0] = 0;
}
void insert(char *str) {
int u = 0, len = strlen (str);
cnt[0]++;
for (int i=0; i<=len; ++i) {
bool found = false;
int v;
for (v=head[u]; v; v=nex[v]) {
if (ch[v] == str[i]) {
found = true; break;
}
}
if (!found) { //插入到链表的头结点后一个
v = sz++;
cnt[v] = 0;
ch[v] = str[i];
nex[v] = head[u];
head[u] = v;
head[v] = 0;
}
u = v; cnt[u]++;
}
}
void query(int u, int dep, ll &res) {
if (!head[u]) {
res += cnt[u] * (cnt[u] - 1) * dep;
return ;
}
int sum = 0, tmp = cnt[u];
for (int v=head[u]; v; v=nex[v]) {
//sum += cnt[v] * (cnt[u] - cnt[v]);
res += cnt[v] * (tmp - cnt[v]) * (dep * 2 + 1);
tmp -= cnt[v];
}
//res += sum / 2 * (2 * dep + 1);
for (int v=head[u]; v; v=nex[v]) {
query (v, dep + 1, res);
}
}
}trie;
char word[M];
int main(void) {
int n, cas = 0;
while (scanf ("%d", &n) == 1) {
if (!n) break;
trie.clear ();
for (int i=0; i<n; ++i) {
scanf ("%s", &word);
trie.insert (word);
}
ll ans = 0;
trie.query (0, 0, ans);
printf ("Case %d: %lld
", ++cas, ans);
}
return 0;
}