我的做法是先建字典树，统计每个结点出现次数和相同字符串个数，每个结点对答案的贡献就是2*C(次数,2)，然后再分别讨论相同字符串和不同字符串对答案的贡献。
另外这题主要就是Trie树的孩子兄弟表示法：
因为数据范围，4000个字符串每个字符串长度1000且字符的范围有62个，用孩子链表表示法最坏，4000*1000*62，再*4Byte，近1GB的内存，太大了，有许多空指针浪费空间。
所以需要用孩子兄弟表示法压缩字典树，4000*1000*2，左孩子右兄弟，用时间换空间。
#include<cstdio>
#include<cstring>
using namespace std;
char key[];
int ch[][],cnt[],flag[],tn;
void insert(char *s){
int x=;
for(int i=; s[i]; ++i){
if(ch[x][]==){
ch[x][]=++tn;
x=ch[x][];
key[x]=s[i];
++cnt[x];
continue;
}
for(x=ch[x][]; key[x]!=s[i] && ch[x][]; x=ch[x][]);
if(key[x]!=s[i]){
ch[x][]=++tn;
x=ch[x][];
key[x]=s[i];
++cnt[x];
}else ++cnt[x];
}
++flag[x];
} int main(){
int t=,n;
char str[];
while(~scanf("%d",&n) && n){
tn=;
memset(key,,sizeof(key));
memset(ch,,sizeof(ch));
memset(cnt,,sizeof(cnt));
memset(flag,,sizeof(flag));
while(n--){
scanf("%s",str);
insert(str);
}
long long res=;
int tot=,sn=;
for(int i=; i<=tn; ++i){
res+=(cnt[i]-)*cnt[i];
if(flag[i]){
res+=(flag[i]-)*flag[i];
tot+=flag[i];
}
}
long long tmp=;
for(int i=; i<=tn; ++i){
if(flag[i]) tmp+=(tot-flag[i])*flag[i];
}
res+=tmp>>;
printf("Case %d: %lld\n",++t,res);
}
return ;
}