Description: 给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。
题解：后缀数组。 两个串的最长公共字串为最大的height值（此height的两个字串属于不同串）。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; const int Maxn=1e5+50; char ch[Maxn*2]; int n,height[Maxn*2],sa[Maxn*2],c[Maxn*2],rk[Maxn*2]; inline void getsa() { int m=27; int *x=rk,*y=height; for(int i=1;i<=n;i++)c[x[i]=ch[i]-'a'+1]++; 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<<=1) { int j=0; for(int i=n-k+1;i<=n;i++)y[++j]=i; for(int i=1;i<=n;i++)if(sa[i]>k)y[++j]=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<=n;i++)c[i]+=c[i-1]; for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i]; swap(x,y); j=x[sa[1]]=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]?j:++j; if(j==n)break; m=j+1; } } inline void getheight() { for(int i=1;i<=n;i++)rk[sa[i]]=i; int k=0,j; for(int i=1;i<=n;height[rk[i++]]=k) for(k?--k:0,j=sa[rk[i]-1];ch[i+k]==ch[j+k];k++); } int main() { scanf("%s",ch+1); n=strlen(ch+1); ch[n+1]=char('z'+1); int m=n; scanf("%s",ch+n+2); n=strlen(ch+2); getsa(); getheight(); int ans=0; for(int i=1;i<=n;i++) { if((sa[i]<=m&&sa[i-1]>=m+2)||(sa[i]>=m+2&&sa[i-1]<=m)) ans=max(ans,height[i]); } printf("%d\n",ans); }