HDU 1403-Longest Common Substring （后缀数组）

# include<iostream>
# include<cstdio>
# include<queue>
# include<cmath>
# include<string>
# include<cstring>
# include<algorithm>
using namespace std;

const int N=100000;

int SA[N*2+5];
int cnt[N*2+5];
int rk[N*2+5];
int tSA[N*2+5];
int height[N*2+5];
int n;
string str;

bool same(int i,int j,int k)
{
	if(tSA[i]!=tSA[j]) return false;
	if(i+k>=n&&j+k<n) return false;
	if(i+k<n&&j+k>=n) return false;
	return tSA[i+k]==tSA[j+k];
}

void buildSA(string s)
{
	int m=27;
	n=s.size();
	for(int i=0;i<m;++i) cnt[i]=0;
	for(int i=0;i<n;++i) ++cnt[rk[i]=s[i]-‘a‘];
	for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;--i) SA[--cnt[rk[i]]]=i;
	for(int k=1;k<=n;k<<=1){
		int p=0;
		for(int i=n-k;i<n;++i) tSA[p++]=i;
		for(int i=0;i<n;++i) if(SA[i]>=k) tSA[p++]=SA[i]-k;
		
		for(int i=0;i<m;++i) cnt[i]=0;
		for(int i=0;i<n;++i) ++cnt[rk[tSA[i]]];
		for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];
		for(int i=n-1;i>=0;--i) SA[--cnt[rk[tSA[i]]]]=tSA[i];
		
		swap(rk,tSA);
		p=1;
		rk[SA[0]]=0;
		for(int i=1;i<n;++i)
			rk[SA[i]]=same(SA[i],SA[i-1],k)?p-1:p++;
		if(p>=n) break;
		m=p;
	}
}

void getHeight()
{
	for(int i=0;i<n;++i) rk[SA[i]]=i;
	int k=0;
	for(int i=0;i<n;++i){
		if(rk[i]==0){
			height[rk[i]]=k=0;
		}else{
			if(k) --k;
			int j=SA[rk[i]-1];
			while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) ++k;
			height[rk[i]]=k;
		}
	}
}

string str1,str2;

bool diff(int i,int j,int m)
{
	if(SA[i]==m||SA[j]==m) return false;
	return (SA[i]-m)/abs(SA[i]-m)*(SA[j]-m)/abs(SA[j]-m)<0;
}

int f(int m)
{
	int ans=0;
	for(int i=1;i<n;++i){
		if(diff(i,i-1,m)&&height[i]>ans)
			ans=height[i];
	}
	return ans;
}

int main()
{
	while(cin>>str1>>str2)
	{
		str=str1+(char)(‘z‘+1)+str2;
		buildSA(str);
		getHeight();
		//cout<<"here is good"<<endl;
		printf("%d\n",f(str1.size()));
	}
	return 0;
}