题意：给你一个长度为n的字符串环，以位置i开始的顺时针长度为n的环构成的字符串有n个，问其中最小字典序的开始位置，有多种解时，输出起始位置最小的。

分析：

首先可以直接拼接两个长度为n的字符串，设原串为S[0],S[1]...S[n-1]则拼接后就是S'=S[0],S[1],...S[n-1],S[0],S[1],...S[n-1]。

那么问题中的n个长度为n的字符串中的任意一个，一定存在S'的某个后缀字符串的前缀与其相等。

我们现在要找最小字典序，则可以直接先求S'的后缀数组SA，然后:

1、找到第一个SA[i]<n的i

2、可以知道SA[i]一定是字典序最小的后缀，但题目要求有多种解时，输出起始位置最小的。

这个怎么搞呢？其实也蛮简单的，对于所有前n个字符字典序相同的后缀字符串，在SA中一定是相邻的。

所以只要判断LCP[i]是不是大于等于n就可以知道该后缀的长度为n个前缀是不是整体上字典序最小的了。

所以可以这么搞：

while（LCP[i]>=n){

　　i++;

　　update(ans);

}

3、输出ans就可以了。其实也可以不update(ans)，最后一个满足LCP[i]>=n的i对应的SA[i]一定是答案。

因为前n个字符相同的所有后缀排在后面的一定比排在前面的长

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define maxn 200001011 #define maxm 201012 #define maxt 11013 #define INF 0x3f3f3f3f14 #define mod 100915 #define MAX_STATE 250016 using namespace std;17 int n,k;18 int Rank[maxn];19 int temp[maxn];20 int LCP[maxn];21 int SA[maxn];22 //比较(rank[k,i],rank[k,i+k])与(rank[k,j],rank[k,j+k])23 bool cmp_sa(int i,int j){24 if(Rank[i]!=Rank[j])return Rank[i]
               
                0)h--;64 for(;j+h
                
                 
                  >t;77 while(t--){78 cin>>S;79 int m = S.length();80 S+=S;81 construct_sa(S,SA);82 construct_lcp(S,SA,LCP);83 int N = 2*m;84 int pos =0;85 int ans;86 for(int i=0;i<=N;++i){87 if(SA[i]
                  
                   =m){94 pos++;95 ans = min(SA[pos]+1,ans);96 }97 cout<
                   
                    <