poj3294 Life Forms（后缀数组）

时间：2021-12-27 07:53:35

【题目链接】

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

【题意】

　　多个字符串求出现超过R次的最长公共子串。

【思路】

二分+划分height，判定一个组中是否包含不小于R个不同字符串的后缀。

需要注意的有：

　　　　　1)      c[]尽量开大，字符范围为“偏移”之后的范围。

　　　　　2)      用kase作为标记节省了每次开始新段需要清零的时间。

　　　　　3)      因为height是sa[i]与sa[i-1]的关系，所以无论是在can的开始还是在新段开始都需要初始为一个串的情况。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<iostream>

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

 using namespace std;

 const int maxn = +;

 int s[maxn];

 int sa[maxn],c[maxn],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;

     }

 }

 int T;

 char a[maxn];

 int f[],kase;

 vector<int> st;

 int can(int limit,int n,int len) {

     int cnt=,ok=;

     st.clear();

     f[sa[]/len]=kase;

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

         if(height[i]<limit) {

             cnt=;

             f[sa[i]/len]=++kase;               //检查每一个组中

         }

         else {

             if(f[sa[i]/len]!=kase) {

                 f[sa[i]/len]=kase;

                 if(cnt>=) cnt++;

                 if(cnt>T/) {

                     ok=;

                     st.push_back(sa[i]);

                     cnt=-;

                 }

             }

         }

     }

     return ok;

 }

 void init() {

     kase=;

     memset(sa,,sizeof(sa));

     memset(f,,sizeof(f));

 }

 int main() {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     while(scanf("%d",&T)== && T) {

         init();

         int len,n=;

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

             scanf("%s",&a);

             len=strlen(a);

             for(int j=;j<len;j++) s[n++]=a[j]+;

             s[n++]=i+;

         }

         n--;

         s[n]=;

         build_sa(,n+);

         getHeight(n);

         int L=,R=len+;

         while(L<R) {

             int M=L+(R-L+)/;

             if(can(M,n,len+)) L=M;

             else R=M-;

         }

         can(L,n,len+);                        //再调用一次求出st

         if(L==) printf("?\n");

         else {

             for(int i=;i<st.size();i++)  {

                 for(int j=st[i];(j-st[i]+)<=L;j++)

                     printf("%c",s[j]-);

                 putchar('\n');

             }

         }

         putchar('\n');

     }

     return ;

 }

相关文章