https://konnyakuxzy.github.io/BZPRO/JudgeOnline/2740.html
题解讲的很清楚了
（好像等于的情况应该归入case2而不是case1？并不确定）
具体方法：
将串翻转，找到字典序最小且最短的后缀，然后找到以这个后缀为纯循环节的最长后缀T，则第一步是将这个后缀T提到最前面；
然后第二步是把整个串除T外部分变为其循环同构串的最小表示。
要找到字典序最小且最短的后缀，只要找到整个串的最小表示法（设最小表示法在位置i开始），然后找到S[i..n]的最短公共前后缀即可（容易发现是对的）（见代码1）；也可以直接用最小表示法类似的方法一次直接求出来（见代码2）
代码1：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii; int T;
char s[];
int f[];
int calc(const char *s,int n)
{
int i=,j=,k=,t;
while(i<n&&j<n&&k<n)
{
t=s[(i+k)%n]-s[(j+k)%n];
if(t==) ++k;
else
{
if(t>) i+=k+;
else j+=k+;
if(i==j) ++j;
k=;
}
}
return min(i,j);
}
int n;
int an1,an2;
int main()
{
int i,j,t;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);n=strlen(s);
reverse(s,s+n);
t=calc(s,n);
//printf("1t%d\n",t);
//t=0;
f[t]=;
for(i=t+,j=;i<n;++i)
{
//j=f[i-1];
while(j>&&s[t+j]!=s[i]) j=f[t+j-];
//printf("2t%d %c %c\n",j,s[t+j],s[i]);
if(s[t+j]==s[i]) ++j;
//printf("1t%d %d %d\n",i,t+j,s[t+j]==s[i]);
f[i]=j;
}
//for(i=t;i<n;++i) printf("%d %d\n",i,f[i]);
j=f[n-];
if(j)
{
while(f[t+j-]>) j=f[t+j-];
t=n-j;
}
//printf("1t%d\n",t);
for(j=t;;)
{
//printf("3t%d %d\n",j-(n-t),t);
if(j>=n-t&&strncmp(s+(j-(n-t)),s+t,n-t)==)
j-=n-t;
else
break;
}
t=j;
//printf("2t%d\n",t);
an1=n-t;
//printf("%d\n",an1);
//printf("%d\n",t);
t=calc(s,t);
an2=n-t;
printf("%d %d\n",an1,an2);
}
return ;
}
代码2：（话说这个复杂度真的对吗？不确定啊？不过实测全a串还有一些随机的串的确是O(n)的，并且能A掉题）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int T;
char s[];
//int f[10000100];
int calc(const char *s,int n)
{
int i=,j=,k=,t;
while(i<n&&j<n&&k<n)
{
t=s[(i+k)%n]-s[(j+k)%n];
if(t==) ++k;
else
{
if(t>) i+=k+;
else j+=k+;
if(i==j) ++j;
k=;
}
}
return min(i,j);
}
int n;
int an1,an2;
int main()
{
int i,j,k,t;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
n=strlen(s);
reverse(s,s+n);
i=;j=;k=;
//int tt=0;
while(i<n&&j<n&&k<n)
{
//++tt;
//printf("1t%d %d %d\n",i,j,k);
t=((i+k<n)?s[i+k]:)-((j+k<n)?s[j+k]:);
if(t==) ++k;
else
{
if(t>) i+=(j+k<n)?k+:k;
else j+=(i+k<n)?k+:k;
if(i==j) ++j;
k=;
}
}
//printf("1t%d\n",tt);
t=min(i,j);
for(j=t;;)
{
if(j>=n-t&&strncmp(s+(j-(n-t)),s+t,n-t)==)
j-=n-t;
else
break;
}
t=j;
an1=n-t;
t=calc(s,t);
an2=n-t;
printf("%d %d\n",an1,an2);
}
return ;
}
https://konnyakuxzy.github.io/BZPRO/JudgeOnline/2176.html
最小表示法板子
这题数据范围比较诡异，一定要用unsigned char。。。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
unsigned char s[];
int calc(const unsigned char *s,int n)
{
int i=,j=,k=,t;
while(i<n&&j<n&&k<n)
{
t=s[(i+k)%n]-s[(j+k)%n];
if(t==) ++k;
else
{
if(t>) i+=k+;
else j+=k+;
if(i==j) ++j;
k=;
}
}
return min(i,j);
}
int n;
int main()
{
int t;
scanf("%d%s",&n,s);
t=calc(s,n);
printf("%s",s+t);
s[t]=;
printf("%s",s);
return ;
}