最大最小表示法
直接上模板,然后求一个最小循环节就好了
#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); } }