大致题意：给你2个字符串，求他们最长公共子串长度
测试案例：
input：
banana cianaic
output：
3
解题思路：将A串和B串进行组合，如A$B这种格式，计算他们的最长公共前缀height的值，然后得出最大且此时的height值的后缀序列分别位于$两侧的值即为结果。（字符串的任何一个子串都是这个字符串的某个后缀的前缀）
代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=200020; int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; int ranks[maxn],height[maxn]; int cmp(int *r,int a,int b,int l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } void da(int *r,int *sa,int n,int m) { int i,j,p,*x=wa,*y=wb,*t; for(i=0; i<m; i++) ws[i]=0; for(i=0; i<n; i++) ws[x[i]=r[i]]++; for(i=1; i<m; i++) ws[i]+=ws[i-1]; for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i; for(p=1,j=1; p<n; j*=2,m=p) { for(p=0,i=n-j; i<n; i++) y[p++]=i; for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0; i<n; i++) wv[i]=x[y[i]]; for(i=0; i<m; i++) ws[i]=0; for(i=0; i<n; i++) ws[wv[i]]++; for(i=1; i<m; i++) ws[i]+=ws[i-1]; for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } return ; } void calheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1; i<=n; i++)ranks[sa[i]]=i; for(i=0; i<n; height[ranks[i++]]=k) for(k?k--:0,j=sa[ranks[i]-1]; r[i+k]==r[j+k]; k++); return; } int main() { char s1[maxn],s2[maxn]; int r[maxn],sa[maxn],i,j; while (scanf("%s%s",s1,s2)==2) { int len1=strlen(s1),len2=strlen(s2); for (i=0;i<len1;i++) r[i]=s1[i]-'a'+1; r[len1]=28; for (i=0;i<len2;i++) r[len1+1+i]=s2[i]-'a'+1; int len=len1+len2+1; r[len]=0; da(r,sa,len+1,29);//29=max(r[i])+1 calheight(r,sa,len); int ans=0; for (i=1;i<=len;i++) { if (height[i]>ans&&((sa[i]<len1&&sa[i-1]>len1)||(sa[i]>len1&&sa[i-1]<len1))) { ans=height[i]; } } printf("%d\n",ans); } return 0; }
