http://acm.hdu.edu.cn/showproblem.php?pid=4333

Problem Description
One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he can put all the digits to the front, so he will get the integer itself. For example, he can change 123 into 312, 231 and 123. Now he wanted to know how many different integers he can get that is less than the original integer, how many different integers he can get that is equal to the original integer and how many different integers he can get that is greater than the original integer. We will ensure that the original integer is positive and it has no leading zeros, but if we get an integer with some leading zeros by revolving the digits, we will regard the new integer as it has no leading zeros. For example, if the original integer is 104, we can get 410, 41 and 104.

Input
The first line of the input contains an integer T (1<=T<=50) which means the number of test cases.
For each test cases, there is only one line that is the original integer N. we will ensure that N is an positive integer without leading zeros and N is less than 10^100000.

Output
For each test case, please output a line which is “Case X: L E G”, X means the number of the test case. And L means the number of integers is less than N that we can get by revolving digits. E means the number of integers is equal to N. G means the number of integers is greater than N.

Sample Input
1
341

Sample Output
Case 1: 1 1 1

前置知识：扩展kmp，我看了这两篇
https://blog.csdn.net/dyx404514/article/details/41831947
https://subetter.com/algorithm/extended-kmp-algorithm.html

题意：给定一个数字串，可以将该串的任意后缀移到前面，问构成的所有新数字中，比原始数小/等/大的各有几个。
思路：首先将原始串s加一倍，变成ss，然后枚举起始点就相当于每次的操作。因为要比较数字大小，只要比较第一位不相等的就行了，这样问题就转化为了：求ss的任意后缀与s的LCP（最长公共前缀），是裸的扩展kmp，最后一个问题，构成的数字有相等的，可以知道，出现重复当且仅当整个字符串存在循环节，那么，根据kmp的失配函数算最短循环节就好了。

#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+100

char T[maxn],P[maxn];
int t,n,m,nxt[maxn],extend[maxn],f[maxn];
int ans1,ans2,ans3;

void getFail()
{
    f[0]=f[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=f[i];
        while(j && P[j]!=P[i])j=f[j];
        f[i+1]=(P[j]==P[i]?j+1:0);
    }
}

void GetNext()
{
    int a=0,p=0;
    nxt[0]=m;
    for(int i=1;i<m;i++)
    {
        if(i-1>=p||i+nxt[i-a]-1>=p)
        {
            if(i-1>=p)p=i-1;
            while(p+1<m && P[p+1]==P[p+1-i])p++;
            a=i;
            nxt[i]=p-i+1;
        }
        else nxt[i]=nxt[i-a];
    }

}

void GetExtend()
{
    GetNext();
    int a=0,p=-1;		//[a,p]闭区间
    for(int i=0;i<n;i++)
    {
        if(i-1>=p || i+nxt[i-a]-1>=p)
        {
            if(i-1>=p)p=i-1;
            while(p+1<n && p+1-i<m && T[p+1]==P[p+1-i])p++;
            a=i;
            extend[i]=p-i+1;
        }
        else extend[i]=nxt[i-a];
    }
}

int main()
{
    cin>>t;
    for(int c=1;c<=t;c++)
    {
        scanf("%s",&T);
        m=strlen(T);
        n=2*m;
        memcpy(P,T,sizeof(char)*m);
        memcpy(T+m,T,sizeof(char)*m);
        ans1=ans2=ans3=0;
        GetExtend();
        for(int i=0;i<m;i++)
        {
            if(extend[i]==m)ans2++;
            else if(T[i+extend[i]]<P[extend[i]])ans1++;
            else ans3++;
        }
        getFail();
        if(m%(m-f[m])==0 && m/(m-f[m])>1)ans1/=(m/(m-f[m])),ans2/=(m/(m-f[m])),ans3/=(m/(m-f[m]));
        printf("Case %d: %d %d %d\n",c,ans1,ans2,ans3);
    }
    return 0;
}