双倍经验过了

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000005;
string S;
int x[maxn],n,y[maxn],sa[maxn],c[maxn],m=150,a[maxn],color[maxn],tmp[maxn],sum[maxn],cnt,maxi,rk[maxn],height[maxn],lg[maxn],s[maxn];
int st[maxn][21];
void getsa()
{
	for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k*=2)
	{
		int tot=0;
		for(int i=n-k+1;i<=n;i++) y[++tot]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++tot]=sa[i]-k;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[x[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		x[sa[1]]=1;tot=1;
		for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?tot:++tot;
		if(tot==n) break;
		m=tot;
	}
}
void getheight()
{
	int k=0;
	for(int i=1;i<=n;i++) rk[sa[i]]=i;
	for(int i=1;i<=n;i++)
	{
		if(rk[i]==1) continue;
		if(k!=0) k--;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
		height[rk[i]]=k;
	}
}
int getans(int l,int r)
{
	if(l==r+1) return 0;
	int k=lg[r-l+1];
//	cout<<k<<"\n";
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
	int t;
	n=-1;
	while(cin>>S)
	{
		t++;
		x[++n]='z'+t;
		s[n]=x[n];
		for(int k=0;k<(int)S.size();k++) x[++n]=S[k],color[n]=t,s[n]=x[n];
	}
//	cout<<"\n";
	getsa();
	getheight();
	for(int i=1;i<=n;i++) tmp[rk[i]]=color[i];
//	for(int i=1;i<=n;i++) cout<<height[i]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<<tmp[i]<<" ";
	for(int i=1;i<=n;i++) st[i][0]=height[i];
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
	int r=1;
	memset(color,0,sizeof(color));
	for(int k=1;k<=lg[n];k++)
		for(int i=1;i+(1<<k)-1<=n;i++)
			st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
	for(int l=1;l<=n;l++)
	{
		if(color[tmp[l]]==0) cnt++;
		color[tmp[l]]++;
//		cout<<color[tmp[l]]<<"\n\n";
		for(;color[tmp[r]]>1;r++){if(color[tmp[r]]==1) cnt--;color[tmp[r]]--;}
//		cout<<l<<" "<<r<<"\n";
		if(cnt==t) maxi=max(maxi,getans(r+1,l));
	}
	cout<<maxi;
	return 0;
}