3.3 字符串（1）

  1 //#define txtout
  2 //#define debug
  3 #include<bits/stdc++.h>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 typedef long long LL;
  7 const double pi=acos(-1.0);
  8 const double eps=1e-8;
  9 const int inf=0x3f3f3f3f;
 10 const int M=4e3+10;
 11 class Trie_tree {   //字典树  前缀树
 12     struct node {
 13         int next[63],ptr,num;// ptr在字典中的位置，num此结点出现几次，
 14         void init() {
 15             ptr=-1;
 16             num=0;
 17             mt(next,0);
 18         }
 19     } s[M*1000];
 20     int ls,p;
 21     int f(char c) {
 22         if(c>='a'&&c<='z') return c-'a';
 23         if(c>='A'&&c<='Z') return c-'A'+26;
 24         if(c>='0'&&c<='9') return c-'0'+52;
 25         return 62;
 26     }
 27 public:
 28     void init() {
 29         s[1].init();
 30         p=0;
 31         ls=2;
 32     }
 33     void Insert(char ch[]) {
 34         int head=1;
 35         for(int k=0; ch[k]; k++) {
 36             int id=f(ch[k]);
 37             if(!s[head].next[id]) {
 38                 s[head].next[id]=ls;
 39                 s[ls++].init();
 40             }
 41             head=s[head].next[id];
 42             s[head].num++;
 43         }
 44         s[head].ptr=p++;
 45     }
 46     int query(char ch[],int op) {
 47         int head=1;
 48         for(int k=0; ch[k]&&head; k++) {
 49             head=s[head].next[f(ch[k])];
 50         }
 51         if(op) { //op==1 查ptr
 52             if(head) return s[head].ptr;
 53             return -1;
 54         } else { //op==0 查num
 55             if(head) return s[head].num;
 56             return 0;
 57         }
 58     }
 59     LL solve(char ch[]){
 60         LL sum=0;
 61         int head=1;
 62         LL presum=-1;
 63         for(int k=0; ch[k]&&head; k++) {
 64             if(presum==-1){
 65                 presum=0;
 66                 for(int i=0;i<63;i++){
 67                     int next=s[head].next[i];
 68                     if(!next) continue;
 69                     presum+=s[next].num;
 70                 }
 71             }
 72             sum+=presum;
 73             head=s[head].next[f(ch[k])];
 74             sum+=s[head].num;
 75             presum=s[head].num;
 76         }
 77         return sum;
 78     }
 79 } trie;
 80 int n;
 81 char a[M][M];
 82 LL solve(){
 83     trie.init();
 84     for(int i=0;i<n;i++){
 85         strcat(a[i],"#");
 86         trie.Insert(a[i]);
 87     }
 88     LL sum=0;
 89     for(int i=0;i<n;i++){
 90         sum+=trie.solve(a[i]);
 91         sum-=strlen(a[i])*2;
 92     }
 93     return sum/2;
 94 }
 95 int main(){
 96     #ifdef txtout
 97     freopen("in.txt","r",stdin);
 98     freopen("out.txt","w",stdout);
 99     #endif // txtout
100     int cas=1;
101     while(~scanf("%d",&n),n){
102         for(int i=0;i<n;i++){
103             scanf("%s",a[i]);
104         }
105         printf("Case %d: %lld
",cas++,solve());
106     }
107     return 0;
108 }