1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<stdlib.h>
  6 #include<math.h>
  7 #include<cstdio>
  8 #include<queue>
  9 #include<stack>
 10 #include<map>
 11 char tt[2*100005];
 12 int extend[2*100005];
 13 int nex[100005];
 14 char d[100005];
 15 char cc[100005];
 16 int pp[100005];
 17 void next1(int k);
 18 void EXkmp(int k,int r);
 19 using namespace std;
 20 int main(void)
 21 {
 22     int i,j,k,p,q;
 23     scanf("%d",&k);
 24     for(int s =1; s<=k; s++)
 25     {
 26         memset(nex,0,sizeof(nex));
 27         memset(extend,0,sizeof(extend));
 28         scanf("%s",d);
 29         int l=strlen(d);
 30         for(i=1; i<=2*l; i++)
 31         {
 32             if(i<=l)
 33                 tt[i]=d[i-1];
 34             else
 35                 tt[i]=d[i-l-1];
 36         }
 37         for(i=0; i<l; i++)
 38             cc[i+1]=d[i];
 39         j=0;
 40         pp[0]=0;
 41         pp[1]=0;
 42         for(i=2; i<=l; i++)
 43         {
 44             while(j>0&&cc[j+1]!=cc[i])
 45             {
 46                 j=pp[j];
 47             }
 48             if(cc[j+1]==cc[i])
 49             {
 50                 j++;
 51             }
 52             pp[i]=j;
 53         }
 54         int temp=l/(l-pp[l]);
 55         if(temp==0)
 56         {
 57             temp=1;
 58         }
 59         next1(l);
 60         EXkmp(2*l,l);
 61         int a[4];
 62         memset(a,0,sizeof(a));
 63         for(i=1; i<=l+1; i++)
 64         {
 65             if(extend[i]==l)//当匹配数等于l时就相等
 66             {
 67                 a[1]++;
 68             }
 69             else
 70             {
 71                 if(tt[i+extend[i]]-‘0‘>cc[extend[i]+1]-‘0‘)//不等于l时比较开始不相等的那位
 72                 {
 73                     a[0]++;
 74                 }
 75                 else a[2]++;
 76             }
 77         }
 78         printf("Case %d: ",s);
 79         printf("%d %d %d\n",a[2]/temp,(a[1]-1)/temp,a[0]/temp);
 80 
 81     }
 82 
 83 }
 84 void next1(int k)
 85 {
 86     int i,j,p;
 87     j=1;
 88     int r=j;
 89     nex[1]=0;
 90     while(cc[j+1]==cc[j]&&j+1<=k)
 91     {
 92         j++;
 93     }
 94     nex[2]=j-r;
 95     int id=2;
 96     for(i=3; i<=k; i++)
 97     {
 98         p=id+nex[id]-1;
 99         int L=nex[i-id+1];
100         int c=i+L-1;
101         if(c>=p)
102         {
103             int j=p-i+1;
104             if(j<0)j=0;
105             while(cc[j+1]==cc[j+i]&&j+i<=k)
106             {
107                 j++;
108             }
109             nex[i]=j;
110             id=i;
111         }
112         else nex[i]=L;
113     }
114 }
115 
116 void EXkmp(int k,int r)
117 {
118     int i,j;
119     j=0;
120     while(cc[j+1]==tt[j+1]&&j+1<=r)
121     {
122         j++;
123     }
124     extend[1]=j;
125     int id=1;
126     int p;
127     for(i=2; i<=k; i++)
128     {
129         p=id+extend[id]-1;
130         int L=nex[i-id+1];
131         int c=i+L-1;
132         if(c>=p)
133         {
134             j=p-i+1;
135             j=max(j,0);
136             while(cc[j+1]==tt[j+i]&&j+i<=k&&j<=r)
137             {
138                 j++;
139             }
140             extend[i]=j;
141             id=i;
142         }
143         else extend[i]=L;
144     }
145 }