1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 #include<vector> 6 using namespace std; 7  8 const int maxn = 4000 * 1000 + 10; 9 int n;10 long long ans;11 12 struct Trie13 {14     int head[maxn];     //head[i]为第i个结点的左儿子编号15     int next[maxn];     //next[i]为第i个结点的右兄弟编号16     char ch[maxn];      //第i个结点上的字符17     int tot[maxn];18     int sz;19 20     void init()21     {22         sz = 1;23         head[0] = tot[0] = next[0] = 0;24     }25 26     void insert(char *s)27     {28         int u = 0, v, n = strlen(s);29         tot[0]++;30         for (int i = 0; i <= n; i++)31         {32             bool found = false;33             for (v = head[u]; v != 0; v = next[v])34             {35                 if (ch[v] == s[i])36                 {37                     found = true;38                     break;39                 }40             }41             if (!found)42             {43                 v = sz++;44                 tot[v] = 0;45                 ch[v] = s[i];46                 next[v] = head[u];47                 head[u] = v;48                 head[v] = 0;49             }50             u = v;51             tot[u]++;52         }53     }54 55     void dfs(int depth, int u)56     {57         if (head[u] == 0)58             ans += tot[u] * (tot[u] - 1)*depth;59         else60         {61             int sum = 0;62             for (int v = head[u]; v != 0; v = next[v])63                 sum += tot[v] * (tot[u] - tot[v]);64             ans += sum / 2 * (2 * depth + 1);65             for (int v = head[u]; v != 0; v = next[v])66                 dfs(depth + 1, v);67         }68     }69 }t;70 71 int main()72 {73     //freopen("D:\\txt.txt", "r", stdin);74     char str[1005];75     int kase = 0;76     while (~scanf("%d", &n), n)77     {78         t.init();79         while (n--)80         {81             scanf("%s", str);82             t.insert(str);83         }84         ans = 0;85         t.dfs(0,0);86         printf("Case %d: %lld\n", ++kase, ans);87     }88     return 0;89 }