扩展KMP，因为是求不同的串，所以相等的串只会出现1次，出现第二次的时候就说明有循环了

Revolving Digits

1
341

Case 1: 1 1 1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=210000;

char T[maxn*2],P[maxn];
int next[maxn],ex[maxn*2];

void pre_exkmp(char P[])
{
    int m=strlen(P);
    next[0]=m;
    int j=0,k=1;
    while(j+1<m&&P[j]==P[j+1]) j++;
    next[1]=j;
    for(int i=2;i<m;i++)
    {
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) next[i]=L;
        else
        {
            j=max(0,p-i-1);
            while(i+j<m&&P[i+j]==P[j]) j++;
            next[i]=j; k=i;
        }
    }
}

void exkmp(char P[],char T[])
{
    memset(ex,0,sizeof(ex));
    memset(next,0,sizeof(next));
    pre_exkmp(P);
    int j=0,k=0;
    int n=strlen(T),m=strlen(P);
    while(j<n&&j<m&&P[j]==T[j]) j++;
    ex[0]=j;
    for(int i=1;i<n;i++)
    {
        int p=ex[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) ex[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&T[i+j]==P[j]) j++;
            ex[i]=j;k=i;
        }
    }
}

int main()
{
    int T_T,cas=1;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%s",P);
    memset(T,0,sizeof(T));
    for(int i=0,m=strlen(P),sz=m*2;i<sz;i++) T[i]=P[i%m];
    exkmp(P,T);
    int ret1=0,ret2=0,ret3=0;
    for(int i=0,m=strlen(P),n=strlen(T);i<n;i++)
    {
        if(ex[i]==m)
        {
            if(ret2==0) ret2=1;
            else break;
        }
        else
        {
            if(T[i+ex[i]]>P[ex[i]]) ret3++;
            else ret1++;
        }
    }
    printf("Case %d: %d %d %d\n",cas++,ret1,ret2,ret3);
}
    return 0;
}

HDOJ 4333 Revolving Digits,布布扣,bubuko.com

HDOJ 4333 Revolving Digits

原文：http://blog.csdn.net/u012797220/article/details/22656847