原题

source: 2012 Multi-University Training Contest 4

题目大意：

题目中给出了一个位数不大于100000位的一个正整数，我们可以不断地把最后一位数字往最前面放，问我们所有可能得到的数当中比原来数大的有几个，比原来数小的有几个，相同的有几个。同时还要注意如果出现

解题思路：

对于处理题当中每个数字往前挪的情况我们采用经典的方法也就是把整个字符串倍增。那么我们利用扩展KMP，以倍增后的串为主串，对于每一个i，如果extend[i]>=len(即输入串的长度)，那么我们就知道这两个串相同，反之的话我们只要匹配第一个失配的那个位二者的大小就能够得到两个字符串的大小。

之后还有一个是去重问题，我们分析发现一旦整个数字出现循环节，那么我们只要对最后的答案除以循环节出现的次数即可

扩展KMP算法详解以及利用KMP求解循环节详解请参见博客：

https://roarboil.github.io/2019/11/21/KMPLoop/

https://roarboil.github.io/2019/11/21/extendkmp/

AC代码

刚开始把数组开小了然后一直wa。。。。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 10000010
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
const int N = 200010;
int exnxt[N];
int extend[2*N];
int nxt[N];
char S[N];
char T[N];
void getNext(){
    int j,k;
    int tlen = strlen(T);
    j=0;
    k=-1;
    nxt[0]=-1;
    while(j<=tlen){
        if(k==-1||T[j]==T[k])
            nxt[++j]=++k;
        else
            k=nxt[k];
    }
}
void ex_GetNext()
{
    int m = strlen(T);
    int a = 0, p = 0;
    exnxt[0] = m;
    
    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + exnxt[i - a] >= p)
        {
            if (i >= p)
                p = i;
            
            while (p < m && T[p] == T[p - i])
                p++;
            
            exnxt[i] = p - i;
            a = i;
        }
        else
            exnxt[i] = exnxt[i - a];
    }
}

/* 求解 extend[] */
void GetExtend()
{
    int a = 0, p = 0;
    int n = strlen(S);
    int m = strlen(T);
    ex_GetNext();
    
    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + exnxt[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;

            while (p < n && p - i < m && S[p] == T[p - i])
                p++;
            
            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = exnxt[i - a];
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    int co=0;
    while (t--)
    {
        co++;
        int lar = 0,eq = 0, sma = 0;
        scanf("%s",T);
        int lent = strlen(T);
        rep(i, lent)
        {
            S[i] = T[i];
            S[i+lent] = T[i];
        }
        getNext();
        int to_div;
        if (nxt[lent] != 0 && lent % (lent-nxt[lent]) == 0)
            to_div = lent / (lent-nxt[lent]);
        else to_div = 1;
        ex_GetNext();
        GetExtend();
        rep(i,lent)
        {
            if (extend[i] >= lent)
                eq ++;
            else if (S[i+extend[i]] > T[extend[i]])
                lar ++;
            else sma ++;
        }
        printf("Case %d: %d %d %d\n",co,sma/to_div,eq/to_div,lar/to_div);
    }
    return 0;
}