神奇的题目诶
原来以为字符串比较一定要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[10000001]; int ans=0,n; int work() { int i=0,j=1,k=0; while(i<n&&j<n) { k=0; while(ch[i+k]==ch[j+k]&&k<n)k++; if(k==n)break; if(ch[i+k]>ch[j+k])i+=k+1; else j+=k+1; if(i==j)++j; } return min(i,j); } int main(){ // freopen("hidden.in","r",stdin); // freopen("hidden.out","w",stdout); scanf("%d",&n); scanf(" "); for(int i=0;i<n;i++) { scanf("%c",&ch[i]); if((i+1)%72==0)scanf(" "); } for(int i=n;i<=2*n-1;i++) ch[i]=ch[i-n]; ans=work(); printf("%d ",ans); // fclose(stdin); // fclose(stdout); }