这题就是一道非常水的题目。 先在这两个串的末尾各加上一个不存在于串中的字符，再将两个串连在一起，用后缀数组得出sa和rank，接着得出height即可求解。
#include<iostream> #include <cstdio> #include <iostream> #include <cstdlib> #include <algorithm> #include <cstring> using namespace std; const int maxn=200010; int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn]; int rank[maxn],height[maxn],s[maxn]; char str[maxn],str1[maxn]; int len1,len2; void init (){ scanf ("%s\n%s",str,str1); len1=strlen (str); len2=strlen (str1); } void make_sa(int n,int m){//make_sa (srelen (s)+1,s中不同字符种类); int i,j,p,*x=wa,*y=wb; for(i=0;i<m;i++) wsf[i]=0; for(i=0;i<n;i++) wsf[x[i]=s[i]]++; for(i=1;i<m;i++) wsf[i]+=wsf[i-1]; for(i=n-1;i>=0;i--) sa[--wsf[x[i]]]=i; for(p=1,j=1;p<n;j<<=1,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++) wsf[i]=0; for(i=0;i<n;i++) wsf[wv[i]]++; for(i=1;i<m;i++) wsf[i]+=wsf[i-1]; for(i=n-1;i>=0;i--) sa[--wsf[wv[i]]]=y[i]; swap (x,y); x[sa[0]]=0; for(p=1,i=1;i<n;i++){ x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]) ? p-1 : p++; } } } void make_height(int n){//make_height (strlen (s)); int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;i++){ if(k)k--; else k=0; j=sa[rank[i]-1]; while(s[i+k]==s[j+k]) k++; height[rank[i]]=k; } } int main(){ init (); int i,n=0; for(i=0;i<len1;i++) s[n++]=str[i]-'a'+1; s[n++]=28; for(i=0;i<len2;i++) s[n++]=str1[i]-'a'+1; s[n]=0; make_sa(n+1,30); make_height(n); int maxx=0; for(i=2;i<n;i++){ if(height[i]>maxx) { if(0<=sa[i-1]&&sa[i-1]<len1&&len1<sa[i]) maxx=height[i]; if(0<=sa[i]&&sa[i]<len1&&len1<sa[i-1]) maxx=height[i]; } } printf("%d\n",maxx); return 0; }