1 #include<cstring> 2 #include<vector> 3 using namespace std; 4 const int maxnode = 4000 * 1000 + 10; 5 const int sigma_size = 26; 6 // 字母表为全体小写字母的Trie 7 struct Trie { 8   int head[maxnode]; // head[i]为第i个结点的左儿子编号 9   int next[maxnode]; // next[i]为第i个结点的右兄弟编号10   char ch[maxnode];  // ch[i]为第i个结点上的字符11   int tot[maxnode];  // tot[i]为第i个结点为根的子树包含的叶结点总数12   int sz; // 结点总数13   long long ans; // 答案14   void clear() {15     sz = 1;16     tot[0] = head[0] = next[0] = 0;17      } // 初始时只有一个根结点18 19   // 插入字符串s（包括最后的‘\0‘），沿途更新tot20   void insert(const char *s) {21     int u = 0, v, n = strlen(s);22     tot[0]++;23     for(int i = 0; i <= n; i++) {24       // 找字符a[i]25       bool found = false;26       for(v = head[u]; v != 0; v = next[v])27         if(ch[v] == s[i]) { // 找到了28           found = true;29           break;30         }31       if(!found) {32         v = sz++; // 新建结点33         tot[v] = 0;34         ch[v] = s[i];35         next[v] = head[u];36         head[u] = v; // 插入到链表的首部37         head[v] = 0;38       }39       u = v;40       tot[u]++;41     }42   }43 44   // 统计LCP=u的所有单词两两的比较次数之和45   void dfs(int depth, int u) {46     if(head[u] == 0) // 叶结点47       ans += tot[u] * (tot[u] - 1) * depth;48     else {49       int sum = 0;50       for(int v = head[u]; v != 0; v = next[v])51         sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其他子树中再选一个52       ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次53       for(int v = head[u]; v != 0; v = next[v])54         dfs(depth+1, v);55     }56   }57 58   // 统计59 long long count() {60     ans = 0;61     dfs(0, 0);62     return ans;63   }64 };65 #include<cstdio>66 const int maxl = 1000 + 10;   // 每个单词最大长度67 int n;68 char word[maxl];69 Trie trie;70 int main() {71   int kase = 1;72   while(scanf("%d", &n) == 1 && n) {73     trie.clear();74     for(int i = 0; i < n; i++) {75       scanf("%s", word);76       trie.insert(word);77     }78     printf("Case %d: %lld\n", kase++, trie.count());79   }80   return 0;81 }