神奇的题目诶
原来以为字符串比较一定要O（NlogN）
结果发现可以均摊O(N)
首先我们来讲一讲原理
我们有3个指针i,j,k
i=0,j=1,k=0
一开始我们不断对k+1直到找到ch[i+k]!=ch[j+k]
那么我们进行判断 如果ch[i+k]>ch[j+k]
那么假设在ch[i]与ch[j]之前的字符串相同，而且我们已知ch[i+1]~ch[i+k-1]与ch[j+1]~ch[j+k-1]的字符串相同，
比较到ch[i+k]与ch[j+k]时，我们会发现ch[j+k]比ch[i+k]更优
所以以ch[i+1]~ch[i+k]为首的字符串一定不是最优解（因为ch[i+k]>ch[j+k]而前面的字符串相同）
所以我们更新i+=k+1;同理，如果ch[j+k]>ch[i+k],j+=k+1;
由于我们最终一定有一个指针超过总长N
所以输出i,j的最小值即可。
但是注意：本题有3个细节：
1、假若i与j重合，那么比较无法继续，所以if(i==j)j++;
2、每次更新指针后要清零重新开始判断
3、由于比较时有可能比较整个字符串，所以要将原字符串复制一遍
时间复杂度均摊O（n）
下面贴代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char ch[];
int ans=,n;
int work()
{
int i=,j=,k=;
while(i<n&&j<n)
{
k=;
while(ch[i+k]==ch[j+k]&&k<n)k++;
if(k==n)break;
if(ch[i+k]>ch[j+k])i+=k+; else j+=k+;
if(i==j)++j;
}
return min(i,j);
}
int main(){
// freopen("hidden.in","r",stdin);
// freopen("hidden.out","w",stdout);
scanf("%d",&n);
scanf("\n");
for(int i=;i<n;i++)
{
scanf("%c",&ch[i]);
if((i+)%==)scanf("\n");
}
for(int i=n;i<=*n-;i++)
ch[i]=ch[i-n];
ans=work();
printf("%d\n",ans);
// fclose(stdin);
// fclose(stdout);
}