题意：
给定a串和b串，求他们的最长公共子串
分析：
把两个串连在一起。构造后缀数组。然后在构造等同于lcp(i-1,i)的height数组。
然后如果相邻的两个后缀分别属于a串和b串，那么就可以做答案。
时间复杂度O(nlgn)
1A
PS:第一次写后缀数组，写得有点繁杂，写多了，就会缩短了。。。
code:
#include
using namespace std;
char s[N],s1[N],s2[N];
struct gtp{int x,data[3],next;}g[N];
int n,len1,len2,sa[N],rank[N],a[N][3],e,ls[N],height[N];
void init(){
scanf("%s",&s1);
scanf("%s",&s2);
len1=strlen(s1);
len2=strlen(s2);
n=0;
for (int i=0;i
s[n]=s1[i];
}
for (int i=0;i
s[n]=s2[i];
}
s[0]=7;
}
void Sort(int l,int r){
if (l>=r) return;
int i=l,j=r;
char mid=s[sa[(l+r)/2]];
do{
while (s[sa[i]]
if (i<=j){
swap(sa[i],sa[j]);
i++; j–;
}
}while (i
Sort(i,r);
}
inline void add(int x,int data[]){
e++;
g[e].x=x;
memcpy(g[e].data,data,sizeof(a[0]));
g[e].next=ls[x];
ls[x]=e;
}
void Jsort(){
e=0;
memset(ls,0,sizeof(int)*(n+2));
for (int i=1;i<=n;i++)
add(a[i][1],a[i]);
int tail=0;
for (int i=0;i<=n;i++){
for (int t=ls[i];t!=0;t=g[t].next){
tail++;
memcpy(a[tail],g[t].data,sizeof(a[0]));
}
}
e=0;
memset(ls,0,sizeof(int)*(n+2));
for (int i=n;i>=1;i–)
add(a[i][0],a[i]);
tail=0;
for (int i=0;i<=n;i++)
for (int t=ls[i];t!=0;t=g[t].next){
tail++;
memcpy(a[tail],g[t].data,sizeof(a[0]));
}
}
inline bool flag(int d1[],int d2[]){
if (d1[0]!=d2[0] || d1[1]!=d2[1]) return true;
return false;
}
void buildarr(){
for (int i=1;i<=n;i++) sa[i]=i;
Sort(1,n);
int t=0;
for (int i=1;i<=n;i++){
if (t==0 || s[sa[i]]!=s[sa[i-1]]) t++;
rank[sa[i]]=t;
}
for (int i=1;1<
a[j][0]=rank[j];
if (j+(1<
}
Jsort();
int t=0;
for (int j=1;j<=n;j++){
if (t==0 || flag(a[j],a[j-1])) t++;
rank[a[j][2]]=t;
}
}
for (int i=1;i<=n;i++) sa[rank[i]]=i;
}
void lcp(){
memset(height,0,sizeof(height));
for (int i=1;i<=n;i++){
if (rank[i]==1) continue;
int st,j,k;
st=max(height[rank[i-1]]-1,0);
j=i+st;
k=sa[rank[i]-1]+st;
while (j<=n && k<=n && s[j]==s[k]){
st++;
j++;
k++;
}
height[rank[i]]=st;
}
}
inline bool part(int k){
if (k<=len1) return true;
return false;
}
void print(){
int ans=0;
for (int i=2;i<=n;i++)
if (part(sa[i-1])^part(sa[i])) ans=max(ans,height[i]);
cout << ans << endl;
}
int main(){
init();
buildarr();
lcp();
print();
}
