题意：给一个数字，每一次把它的最后一位拿到最前面，一直那样下去，分别求形成的数字小于，等于和大于原来数的个数。
SAM乱搞失败
当然要先变SS了
然后考虑每个后缀前长为n个字符，把它跟S比较就行了
如果用后缀家族的话复杂度要加上log，本题会TLE吧
求一个串S的每个后缀与另一个串T的最长公共前缀可以用扩展KMP！复杂度O(n+m)
看课件吧
从1开始写真不容易以后再也不从1开始了，判断位置好麻烦好容易错
next[i]=LCP(T[i,m],T)
extend[i]=LCP(S[i,n],T)
主要思想就是求i时记录p=max{a+extend[a]-1},1<=a<i 也就是当前最远匹配到哪里，这么做是为了以后直接利用next的信息
S[a,a+extend[a]-1]--->T[1,extend[a]-1]是一样的
那么从i开始的后缀的前一部分是和T[i-a+1..]相同的，就不用比较了因为已经有L=next[i-a+1]了
如果i+L-1<p，extend[i]=L
否则从s[p+1]和t[p-i+1+1]开始暴力往后匹配，并更新a
注意：本题要求不相同的数字，出现相同数字说明有循环节，KMP求一下看看有没有可以整除的循环节
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int n,m;
int next[N],extend[N];
char s[N],t[N];
void getNext(char s[],int n){
//printf("getNext %d\n",n);
//for(int i=1;i<=n;i++) printf("%c",s[i]); next[]=n;
int a=;
while(a<n&&s[a]==s[a+]) a++;
next[]=a-;
a=;
for(int i=;i<=n;i++){
int p=a+next[a]-,L=next[i-a+];
if(i+L-<p) next[i]=L;
else{
int j=max(p-i+,);//!!
while(i+j<=n&&s[i+j]==s[j+]) j++;
next[i]=j;a=i;
}
}
//for(int i=1;i<=n;i++) printf("next %d %d\n",i,next[i]);
}
void getExtend(char s[],char t[]){
//printf("getExtend %d\n",n);
//for(int i=1;i<=n;i++) printf("%c",s[i]);puts("");
getNext(t,m);
int mn=min(n,m),a=;
while(a<=mn&&s[a]==t[a]) a++;
extend[]=a-;
a=;
for(int i=;i<=n;i++){
int p=a+extend[a]-,L=next[i-a+];
if(i+L-<p) extend[i]=L;
else{
int j=max(p-i+,);
while(i+j<=n&&s[i+j]==t[j+]) j++;
extend[i]=j;
a=i;
}
}
//for(int i=1;i<=n;i++) printf("extend %d %d\n",i,extend[i]);
}
int fail[N];
void getFail(char s[],int n){
fail[]=;
for(int i=;i<=n;i++){
int j=fail[i-];
while(j&&s[j+]!=s[i]) j=fail[j];
fail[i]=s[j+]==s[i]?j+:;
}
}
int L,E,G;
void solve(){
getExtend(s,t);
L=E=G=;
for(int i=;i<=m;i++){
int lcp=extend[i];
if(lcp>=m) E++;
else if(t[+lcp]<s[i+lcp]) G++;
else L++;
}
//for(int i=1;i<=n;i++) printf("hi %d %d %d\n",i,next[i],extend[i]);
getFail(t,m);
int _=m%(m-fail[m])==?m/(m-fail[m]):;
L/=_;E/=_;G/=_;
} int main(){
freopen("in","r",stdin);
int T=read(),cas=;
while(T--){
scanf("%s",s+);
n=m=strlen(s+);
for(int i=;i<=n;i++) s[i+n]=t[i]=s[i];
n<<=;
solve();
printf("Case %d: %d %d %d\n",++cas,L,E,G);
}
}