Description

給出兩個字符串 a，b ，求 a 和 b 的最大公共子串，字符串長度為 500000。

Solution

• 可以用后綴數(shù)組做，將兩個字符串接起來，中間用特殊的分隔符相連。

• 求出 Height 數(shù)組之后，就可以利用 Height 數(shù)組的性質(zhì)進行計算了！

• 對于一個 i ，如果 sa[i] 和 sa[i?1] 的位置分別屬于 a 和 b ，那么 height[i] 就是合法的。

• 求最大值即可。時間復(fù)雜度 O(N?log?N) 。

Code

#include<cstdio> using namespace std; const int N=5e5+5; int n,m=27,len,ans; int sa[N],rank[N],r1[N],height[N],tax[N]; int s[N]; inline void readln() {char ch=getchar();while(ch<'a' || ch>'z') ch=getchar();while(ch>='a' && ch<='z') s[++n]=ch-'a'+1,ch=getchar(); } inline void csort() {for(int i=1;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) tax[rank[i]]++;for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i;i--) sa[tax[rank[r1[i]]]--]=r1[i]; } inline void SA() {for(int i=1;i<=n;i++) rank[r1[i]=i]=s[i];csort();for(int j=1,p=0;j<=n;j<<=1,m=p,p=0){for(int i=n-j+1;i<=n;i++) r1[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>j) r1[++p]=sa[i]-j;csort();for(int i=1;i<=n;i++) r1[i]=rank[i];rank[sa[1]]=p=1;for(int i=2;i<=n;i++)rank[sa[i]]=(r1[sa[i]]==r1[sa[i-1]] && r1[sa[i]+j]==r1[sa[i-1]+j])?p:++p;}for(int i=1,lcp=0;i<=n;height[rank[i++]]=lcp){if(lcp) lcp--;while(s[i+lcp]==s[sa[rank[i]-1]+lcp]) lcp++;} } int main() {readln(),s[len=++n]=m,readln(),SA();for(int i=2;i<=n;i++)if(height[i]>ans && sa[i]<len^sa[i-1]<len) ans=height[i];printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的SPOJ 1811. POJ 2774 . 最大公共子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。