poj2774 Long Long Message（后缀数组）

时间：2023-03-09 16:28:26
poj2774 Long Long Message（后缀数组）

【题目链接】

　　http://poj.org/problem?id=2774

【题意】

　　A & B的最长公共子序列。　　

【思路】

拼接+height数组。将AB拼接成一个形如A$B的串，枚举height数组并判断sa[i]是否与sa[i-1]分别属于两个不同的字符串，如果是则比较得ans。

　　 时间复杂度为O(nlogn)。

Ps：注意不能直接取height的最大值，因为取到的两个后缀的lcp可能同处于一个字符串。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 const int maxn = +;

 const int maxm = ;

 int s[maxn];

 int sa[maxn],c[maxm],t[maxn],t2[maxn];

 void build_sa(int m,int n) {

     int i,*x=t,*y=t2;

     for(i=;i<m;i++) c[i]=;

     for(i=;i<n;i++) c[x[i]=s[i]]++;

     for(i=;i<m;i++) c[i]+=c[i-];

     for(i=n-;i>=;i--) sa[--c[x[i]]]=i;

     for(int k=;k<=n;k<<=) {

         int p=;

         for(i=n-k;i<n;i++) y[p++]=i;

         for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

         for(i=;i<m;i++) c[i]=;

         for(i=;i<n;i++) c[x[y[i]]]++;

         for(i=;i<m;i++) c[i]+=c[i-];

         for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=; x[sa[]]=;

         for(i=;i<n;i++)

             x[sa[i]]=y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]?p-:p++;

         if(p>=n) break;

         m=p;

     }

 }

 int rank[maxn],height[maxn];

 void getHeight(int n) {

     int i,j,k=;

     for(i=;i<=n;i++) rank[sa[i]]=i;

     for(i=;i<n;i++) {

         if(k) k--;

         j=sa[rank[i]-];

         while(s[j+k]==s[i+k]) k++;

         height[rank[i]]=k;

     }

 }

 char a[maxn],b[maxn];

 int n;

 int main() {

     scanf("%s%s",a,b);

     int lena=strlen(a),lenb=strlen(b);

     n=lena+lenb+;

     for(int i=;i<lena;i++) s[i]=a[i]; s[lena]=;

     for(int i=;i<lenb;i++) s[lena+i+]=b[i];

     s[n]=;

     build_sa('z'+,n+);

     getHeight(n);

     int ans=;

     for(int i=;i<=n;i++) {

         int k=;

         k+=sa[i]<lena?:;

         k+=sa[i-]<lena?:;

         if(k==) ans=max(ans,height[i]);

     }

     printf("%d\n",ans);

     return ;

 }

UPD.16/4/6

当然也可以用SAM搞一搞，写起来更简单些

相关文章