因为字符集比较大，所以就不能用简单字典树，在字典树里面，用链表进行存储。这个倒是不难，练了下手
统计的时候还是有点难搞，因为要算所有的两两比较的次数之和，对分叉处进行计算，注意细节
#include#include #include using namespace std;const int N = 4000*1000+10;struct Trie{ int head[N]; int next[N]; char ch[N]; int tot[N]; int sz; long long ans; void clear() { sz=1; head[0]=next[0]=tot[0]=0; ans=0; } void insert(const char* s) { int u=0,v,len; len=strlen(s); tot[0]++; for (int i=0; i<=len; 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++; ch[v]=s[i]; tot[v]=0; next[v]=head[u]; head[u]=v; head[v]=0; } u=v; tot[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]); ans += sum / 2 * (2 * depth + 1); for(int v = head[u]; v != 0; v = next[v]) dfs(depth+1, v); } } long long count() { ans = 0; dfs(0, 0); return ans; }} T;char str[1010];int main(){ int n; int kase=0; while (scanf("%d",&n) && n) { T.clear(); for (int i=1; i<=n; i++) { scanf("%s",str); T.insert(str); } T.count(); printf("Case %d: %lld\n",++kase,T.ans); } return 0;}