hdu 4333 Revolving Digits (扩展KMP)

Problem DescriptionOne 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

hncu__lz

240人浏览 · 2016-10-20 21:50:29

hncu__lz · 2016-10-20 21:50:29 发布

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

Sample Output

  
  
   
   Case 1: 1 1 1

题意：就是给你一个数字，然后把最后一个数字放到最前面去，经过几次变换后又回到原数字，问在这些数字中，比原数字小的，相等的，大的分别有多少个，需要注意前面已经比较过的不能再比较。比如341-->134-->413-->341,所以和原数字相比，比原数字小的有一个，相等的有一个，大的有一个。

思路：

由于数字太大，我们转换成字符串；

可以先将字符串与本身连接起来得到一个字符串，在与原串进行扩展KMP；我的没有连接，直接用给的字符串求扩展KMP中的next数组，然后比较判断得出结果；

难点在于如何让去重，我们可以用KMP中的next数组得到循环节长度，然后去重得到结果；

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000005;
char c[N];
int nex[N],len,ex[N];
int getex()
{
    int i=0,j=-1;
    ex[0]=-1;
    while(i<len)
    {
        if(j==-1||c[i]==c[j])
            ex[++i]=++j;
        else
            j=ex[j];
    }
    return ex[len];
}
void getnext()
{
    int i=0;
    nex[0]=len;
    while(c[i]==c[i+1]&&i<len-1)
        i++;
    nex[1]=i;
    int po=1;
    for(i=2;i<len;i++)
    {
        if(nex[i-po]+i<po+nex[po])
            nex[i]=nex[i-po];
        else
        {
            int j=po+nex[po]-i;
            if(j<0)
                j=0;
            while(i+j<len&&c[i+j]==c[j])
                j++;
            nex[i]=j;
            po=i;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        int s1=0,s2=0,s3=0;
        scanf("%s",c);
        len=strlen(c);
        int l=len-getex();
        int s;
        if(len%l)
            s=1;
        else
            s=len/l;
        getnext();
        for(int i=0;i<len;i++)
        {
            if(nex[i]<len-i)
            {
                if(c[nex[i]]>c[i+nex[i]])
                    s3++; //比原串小
                else
                    s1++; //比原串大；
            }
            else
            {
                if(nex[len-i]<i)
                {
                    if(c[nex[len-i]+len-i]>c[nex[len-i]])
                        s3++;
                    else
                        s1++;
                }
                else
                    s2++;
            }
        }
        printf("Case %d: ",t);
        printf("%d %d %d\n",s3/s,s2/s,s1/s);
    }
}