后缀自动机题解 -> http://www.cnblogs.com/SilverNebula/p/6420601.html

后缀自动机敲完，看了下排行，wc为什么别人跑得这么快？……是诶，这最小表示法用后缀自动机当然慢了

依稀记得最小表示法有超快的算法，于是去查了查，有$O(n)$的算法 (后缀自动机均摊也是$O(n)$然而常数大)

找到了这篇讲解-> http://www.cnblogs.com/mjy0724/p/4625928.html

 

这样就跑得飞快了(380ms，不知道那些几十ms的怎么跑出来的)

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 using namespace std; 8 const int mxn=600010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<'0' || ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 int n,a[mxn];16 int solve(){17     int i,j,ed=n*2;18     i=1;j=2;19     while(i<=n && j<=n){20         int k=0;21         while(j+k<=ed && a[i+k]==a[j+k])k++;22         if(j+k>ed)break;23         if(a[i+k]>a[j+k]){24             i=max(j,i+k+1);25             j=i+1;26         }27         else j=j+k+1;28     }29     return min(i,j);30 }31 int main(){32     int i,j;33     n=read();34     for(i=1;i<=n;i++){35         a[i]=read();a[i+n]=a[i];36     }37     int ans=solve();38     int ed=ans+n-1;39     for(i=ans;i