把第二个串连到第一个上，求一下后缀数组，然后处理height的时候，判断是不是当前位置和上一个位置处在原来的不同串就好了（而且不能只判断一个串内，只到n1会掉下 (i>n1 && j<=n1)这种情况。。。）
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define N 100005<<2 5 #define LL long long 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 inline int ra() 9 { 10 int x=0,f=1; char ch=getchar(); 11 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 12 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 13 return x*f; 14 } 15 char ch[N],ch1[N],ch2[N]; 16 int n,k,p,q,n1,n2,ans; 17 int a[N],rank[2][N],sa[2][N],h[N],v[N]; 18 void cal_sa(int sa[N], int rank[N], int Sa[N], int Rank[N]) 19 { 20 for (int i=1; i<=n; i++) v[rank[sa[i]]]=i; 21 for (int i=n; i>=1; i--) 22 if (sa[i]>k) Sa[v[rank[sa[i]-k]]--]=sa[i]-k; 23 for (int i=n-k+1; i<=n; i++) Sa[v[rank[i]]--]=i; 24 for (int i=1; i<=n; i++) Rank[Sa[i]]=Rank[Sa[i-1]]+(rank[Sa[i]]!=rank[Sa[i-1]] || rank[Sa[i]+k]!=rank[Sa[i-1]+k]); 25 } 26 void get_height() 27 { 28 k=0; 29 for (int i=1; i<=n; i++) //只到n1会掉下 (i>n1 && j<=n1)这种情况。。。 30 { 31 if (rank[p][i]==1) h[1]=0; 32 else{ 33 int j=sa[p][rank[p][i]-1]; 34 while (a[i+k]==a[j+k]) k++; 35 if ((j>n1 && i<=n1) || (i>n1 && j<=n1)) ans=max(ans,k); 36 h[rank[p][i]]=k; if (k>0) k--; 37 } 38 } 39 } 40 void work() 41 { 42 p=0,q=1; 43 for (int i=1; i<=n; i++) v[a[i]]++; 44 for (int i=1; i<=30; i++) v[i]+=v[i-1]; 45 for (int i=1; i<=n; i++) sa[p][v[a[i]]--]=i; 46 for (int i=1; i<=n; i++) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]); 47 for (k=1; k<n; k<<=1,q^=1,p^=1) cal_sa(sa[p],rank[p],sa[q],rank[q]); 48 get_height(); 49 } 50 int main() 51 { 52 scanf("%s",ch1+1); scanf("%s",ch2+1); 53 n1=strlen(ch1+1); n2=strlen(ch2+1); n=n1+n2; 54 for (int i=1; i<=n1; i++) a[i]=ch1[i]-'a'+1; 55 for (int i=n1+1; i<=n; i++) a[i]=ch2[i-n1]-'a'+1; 56 work(); 57 cout<<ans; 58 return 0; 59 }