题意

给出一个长度为 \(n\) 的数字，每次可以将最后一位放到前面，那么一共会有 \(n\) 个数字，问有几个不同的数字比原来的数字大，小或相等。

分析

将字符串扩展到原来的两倍，然后求一发 EXKMP ，得到 \(nxt\) 数组表示后缀串与整个串的最长公共前缀长度，那么要么有下个一个字符不同，或者全部相同，对于后者判断是否产生了循环节，对于前者直接比较大小即可。

注意求的是有几个不同的数字，所以一旦发现存在最小长度的循环节后就要退出循环。

code

#include 
    
     using namespace std;// 调用前// nxt[0] = 0;// exkmp(s2 + 1, s2, nxt + 1, nxt); // s2 作为模板串// exkmp(s1, s2, ex, nxt);// O(n+m)的复杂度下求出字符串s1的任意后缀与字符串s2的最长公共前缀// nxt[i]==j 表示s2的以s2[i]为起始的后缀与串本身的最长公共前缀长度j// ex[i]为s1[i..]与s2的最长公共前缀，nxt[i]为s2[i..]与s2的最长公共前缀void exkmp(char s1[], char s2[], int ex[], int nxt[]) {    int i = 0, j = 0, p = -1;    while(s1[i]) {        if(p == -1) {            j = 0;            do p++;            while(s1[i + p] && s1[i + p] == s2[j + p]);            ex[i] = p;        } else if(nxt[j] != p) ex[i] = min(p, nxt[j]);        else {            j = 0;            while(s1[i + p] && s1[i + p] == s2[j + p]) p++;            ex[i] = p;        }        i++; j++; p--;    }    ex[i] = 0;}const int MAXN = 2e5 + 10;char s[MAXN];int nxt[MAXN];int main() {    int T;    scanf("%d", &T);    for(int kase = 1; kase <= T; kase++) {        nxt[0] = 0;        scanf("%s", s);        int len = strlen(s);        for(int i = len; i < 2 * len; i++) s[i] = s[i - len];        s[2 * len] = 0;        exkmp(s + 1, s, nxt + 1, nxt);        int L = 0, G = 0;        for(int i = 1; i < len; i++) {            int x = nxt[i];            if(min(x, len - i) + i == len && len % i == 0) { // 说明存在循环节，那么后面都是重复的                break;            }            if(x < len) {                if(s[x] < s[i + x]) G++;                else L++;            }        }        printf("Case %d: %d 1 %d\n", kase, L, G);    }    return 0;}