【题目链接】
http://poj.org/problem?id=2774
【题意】
A & B的最长公共子序列。
【思路】
拼接+height数组。将AB拼接成一个形如A$B的串，枚举height数组并判断sa[i]是否与sa[i-1]分别属于两个不同的字符串，如果是则比较得ans。
时间复杂度为O(nlogn)。
Ps：注意不能直接取height的最大值，因为取到的两个后缀的lcp可能同处于一个字符串。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 5 using namespace std; 6 7 const int maxn = 300000+10; 8 const int maxm = 150; 9 10 int s[maxn]; 11 int sa[maxn],c[maxm],t[maxn],t2[maxn]; 12 13 void build_sa(int m,int n) { 14 int i,*x=t,*y=t2; 15 for(i=0;i<m;i++) c[i]=0; 16 for(i=0;i<n;i++) c[x[i]=s[i]]++; 17 for(i=1;i<m;i++) c[i]+=c[i-1]; 18 for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i; 19 20 for(int k=1;k<=n;k<<=1) { 21 int p=0; 22 for(i=n-k;i<n;i++) y[p++]=i; 23 for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; 24 25 for(i=0;i<m;i++) c[i]=0; 26 for(i=0;i<n;i++) c[x[y[i]]]++; 27 for(i=0;i<m;i++) c[i]+=c[i-1]; 28 for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; 29 30 swap(x,y); 31 p=1; x[sa[0]]=0; 32 for(i=1;i<n;i++) 33 x[sa[i]]=y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++; 34 if(p>=n) break; 35 m=p; 36 } 37 } 38 int rank[maxn],height[maxn]; 39 void getHeight(int n) { 40 int i,j,k=0; 41 for(i=0;i<=n;i++) rank[sa[i]]=i; 42 for(i=0;i<n;i++) { 43 if(k) k--; 44 j=sa[rank[i]-1]; 45 while(s[j+k]==s[i+k]) k++; 46 height[rank[i]]=k; 47 } 48 } 49 50 char a[maxn],b[maxn]; 51 int n; 52 53 int main() { 54 scanf("%s%s",a,b); 55 int lena=strlen(a),lenb=strlen(b); 56 n=lena+lenb+1; 57 for(int i=0;i<lena;i++) s[i]=a[i]; s[lena]=1; 58 for(int i=0;i<lenb;i++) s[lena+i+1]=b[i]; 59 s[n]=0; 60 61 build_sa('z'+1,n+1); 62 getHeight(n); 63 64 int ans=0; 65 for(int i=2;i<=n;i++) { 66 int k=0; 67 k+=sa[i]<lena?1:2; 68 k+=sa[i-1]<lena?1:2; 69 if(k==3) ans=max(ans,height[i]); 70 } 71 printf("%d ",ans); 72 return 0; 73 }
UPD.16/4/6
当然也可以用SAM搞一搞，写起来更简单些