1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200000+514 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 int n,c[maxn],sa[maxn],rk[maxn],h[maxn],t[maxn],t2[maxn];32 char s[maxn];33 void build(int m)34 {35     int *x=t,*y=t2;36     for0(i,m)c[i]=0;37     for0(i,n)c[x[i]=s[i]]++;38     for1(i,m)c[i]+=c[i-1];39     for3(i,n,0)sa[--c[x[i]]]=i;40     for(int k=1;k<=n+1;k<<=1)41     {42         int p=0;43         for2(i,n-k+1,n)y[p++]=i;44         for0(i,n)if(sa[i]>=k)y[p++]=sa[i]-k;45         for0(i,m)c[i]=0;46         for0(i,n)c[x[y[i]]]++;47         for1(i,m)c[i]+=c[i-1];48         for3(i,n,0)sa[--c[x[y[i]]]]=y[i];49         swap(x,y);50         p=1;x[sa[0]]=0;51         for1(i,n)x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;52         if(p>=n+1)break;53         m=p-1;54     }55 }56 void calch()57 {58     for1(i,n)rk[sa[i]]=i;59     for(int i=0,k=0,j;i<n;h[rk[i++]]=k)60      for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);61 }62 int main()63 {64     freopen("input.txt","r",stdin);65     freopen("output.txt","w",stdout);66     n=read();int len=0;67     while(len<n)68     {69         scanf("%s",s+len);70         len=strlen(s);71     }72     for0(i,n-1)s[n+i]=s[i];73     n<<=1;74     s[n]=‘ ‘;75     build(128);76     calch();77     for1(i,n>>1)if(sa[i]<n/2){printf("%d\n",sa[i]);return 0;}78     return 0;79 }