洛谷:

SPOJ: 代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char S[1000000],str[1000000];
int n,nn,m;
int rk[1000000],sa[1000000],sa2[1000000],tax[1000000],height[1000000];
int pos[1000000],lst[1000000];
int Q[1000000],tm[1000000],frt,rer;
int tot[10];
void qsort(){
	for(int i=0;i<=m;i++)tax[i]=0;
	for(int i=1;i<=n;i++)tax[rk[i]]++;
	for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
	for(int i=n;i>=1;i--)sa[tax[rk[sa2[i]]]--]=sa2[i];
}
void suffix(){
	m=30;
	for(int i=1;i<=n;i++)rk[i]=S[i]-'a'+2,sa2[i]=i;
	qsort();
	for(int j=1,cnt=0;j<n;m=cnt,j<<=1){
		cnt=0;
		for(int i=n-j+1;i<=n;i++)sa2[++cnt]=i;
		for(int i=1;i<=n;i++)if(sa[i]>=j+1)sa2[++cnt]=sa[i]-j;
		qsort();
		for(int i=0;i<=n;i++)sa2[i]=rk[i];
		rk[sa[1]]=1;cnt=1;
		for(int i=2;i<=n;i++){
			if(sa2[sa[i-1]]!=sa2[sa[i]]||sa2[sa[i-1]+j]!=sa2[sa[i]+j])cnt++;
			rk[sa[i]]=cnt;
		}
	}
}
void calheight(){
	int i,j,k=0;
	for(i=1;i<=n;height[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];S[i+k]==S[j+k];k++);
	return;
}
int chk(int len){
	int res=-1,sum=0;
	frt=1;rer=0;
	for(int i=1;i<=5;i++)tot[i]=0;
	tot[pos[sa[1]]]++;
	if(pos[sa[1]]>=1&&tot[pos[sa[1]]]==1)sum++;
	for(int i=2;i<=len;i++){
		tot[pos[sa[i]]]++;
		if(pos[sa[i]]>=1&&tot[pos[sa[i]]]==1)sum++;
		while(rer-frt>=0&&Q[rer]>=height[i])rer--;
		Q[++rer]=height[i];tm[rer]=i;
		if(sum==nn)res=max(res,Q[frt]);
	}
	for(int i=len+1;i<=n;i++){
		tot[pos[sa[i-len]]]--;
		if(pos[sa[i-len]]>=1&&tot[pos[sa[i-len]]]==0)sum--;
		while(rer-frt>=0&&i-len>=tm[frt]-1)frt++;

		tot[pos[sa[i]]]++;
		if(pos[sa[i]]>=1&&tot[pos[sa[i]]]==1)sum++;
		while(rer-frt>=0&&Q[rer]>=height[i])rer--;
		Q[++rer]=height[i];tm[rer]=i;

		if(sum==nn)res=max(res,Q[frt]);
	}
	return res;
}
int main(){//freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	nn=2;
	for(int i=1;i<=nn;i++){
		scanf("%s\n",str+1);
		for(int j=1;j<=strlen(str+1);j++)S[++n]=str[j],pos[n]=i;
		S[++n]='a'-1;lst[n]=n;
	}
	for(int i=n;i>=1;i--)if(lst[i]==0)lst[i]=lst[i+1];
	suffix();
	calheight();
	for(int i=1;i<=n;i++)
		height[i]=min(height[i],min(lst[sa[i]]-sa[i],lst[sa[i-1]]-sa[i-1]));
	int ans=0;
	for(int i=2;i<=n;i++){
		if(pos[sa[i]]*pos[sa[i-1]]!=2)continue;
		ans=max(ans,height[i]);
	}
	printf("%d\n",ans);
	return 0;
}

求助大佬