最大最小表示法

直接上模板,然后求一个最小循环节就好了

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 1e6+100;
int getminstring(char s[]){
    int nn = strlen(s);
    int i=0,j=1,k=0;
    while (i<nn&&j<nn&&k<nn){
        if (s[(i+k)%nn]==s[(j+k)%nn])++k;
        else if (s[(i+k)%nn]>s[(j+k)%nn])i=i+k+1,k=0;
        else if (s[(i+k)%nn]<s[(j+k)%nn])j=j+k+1,k=0;
        if (i==j)++j;
    }return min(i,j);
}
int getmaxstring(char s[]){
    int nn = strlen(s);
    int i=0,j=1,k=0;
    while (i<nn&&j<nn&&k<nn){
        if (s[(i+k)%nn]==s[(j+k)%nn])++k;
        else if (s[(i+k)%nn]<s[(j+k)%nn])i=i+k+1,k=0;
        else if (s[(i+k)%nn]>s[(j+k)%nn])j=j+k+1,k=0;
        if (i==j)++j;
    }return min(i,j);
}
int net[max_n];
void getnext(char p[]){
    int nn=strlen(p);
    net[0]=-1;
    for (int i=0,j=-1;i<nn;){
        if (j==-1||p[i]==p[j])net[++i]=++j;
        else j=net[j];
    }
} 
char s[max_n];
int main(){
    while (~scanf("%s",s)){
        getnext(s);int n = strlen(s);
        int mi=getminstring(s);
        int ma=getmaxstring(s);
        int cyc = n-net[n];
        int cycnum = 1;
        if (cyc>0&&n%cyc==0)cycnum=n/cyc;
        printf("%d %d %d %d\n",mi+1,cycnum,ma+1,cycnum);
    }
}