【POJ3294】 Life Forms （后缀数组+二分）

【题意】

　　给定n个字符串，求出现在大于n/2个字符串中的最长子串。

【分析】

　　把n个串拼起来，中间插入不同的特殊字符（注意要不同的）。然后求height数组。

　　二分答案，根据二分的L分组，统计组内有多少个来自不同的串即可。

　　最后输出的字符串要按字典序，不过不用排序，因为求出的sa表示它已经排好序了，所以就按照顺序输入就好了。

　　傻逼的我RE了很久竟然是数组大小开的混乱~~呵呵~~

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 410

 #define Maxl 4010

 #define Ml 400010

 int c[Ml];

 int n,cl;

 char s[Maxl];

 int p[Ml];

 void init()

 {

     cl=;

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

     {

         scanf("%s",s);

         int l=strlen(s);

         for(int j=;j<l;j++) c[++cl]=s[j]-'a'+,p[cl]=i;

         c[++cl]=+i,p[cl]=;

     }

 }

 int sa[Ml],rk[Ml],Rs[Ml],y[Ml],wr[Ml];

 void get_sa(int m)

 {

     memcpy(rk,c,sizeof(rk));

     for(int i=;i<=m;i++) Rs[i]=;

     for(int i=;i<=cl;i++) Rs[rk[i]]++;

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

     for(int i=cl;i>=;i--) sa[Rs[rk[i]]--]=i;

     int ln=,p=;//p表示目前有多少个不一样的rk

     while(p<cl)

     {

         int k=;

         for(int i=cl-ln+;i<=cl;i++) y[++k]=i;

         for(int i=;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;

         for(int i=;i<=cl;i++) wr[i]=rk[y[i]];

         for(int i=;i<=m;i++) Rs[i]=;

         for(int i=;i<=cl;i++) Rs[wr[i]]++;

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

         for(int i=cl;i>=;i--) sa[Rs[wr[i]]--]=y[i];

         for(int i=;i<=cl;i++) wr[i]=rk[i];

         for(int i=cl+;i<=cl+ln;i++) wr[i]=;

         p=,rk[sa[]]=;

         for(int i=;i<=cl;i++)

         {

             if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;

             rk[sa[i]]=p;

         }

         ln*=;m=p;

     }

     sa[]=rk[]=;

 }

 int height[Ml];

 void get_he()

 {

     int k=;

     for(int i=;i<=cl;i++) if(rk[i]!=)

     {

         int j=sa[rk[i]-];

         if(k) k--;

         while(c[i+k]==c[j+k]&&i+k<=cl&&j+k<=cl) k++;

         height[rk[i]]=k;

     }

 }

 bool inq[Maxn];

 queue<int > q;

 int ans[][Ml],now;

 bool check(int x)

 {

     if(x==) return ;

     ans[-now][]=;

     int cnt=;

     bool ok=;

     for(int i=;i<=cl-n;i++)

     {

         if(!inq[p[sa[i]]])

         {

             q.push(p[sa[i]]);

             inq[p[sa[i]]]=;

             cnt++;

         }

         if(height[i+]<x)//new group

         {

             if(cnt>n/&&cnt!=) ok=,ans[-now][++ans[-now][]]=sa[i];

             cnt=;

             while(!q.empty()) {inq[q.front()]=;q.pop();}

         }

     }

     if(ok) now=-now;

     return ok;

 }

 void ffind()

 {

     now=;

     while(!q.empty()) q.pop();

     memset(inq,,sizeof(inq));

     int l=,r=cl;

     while(l<r)

     {

         int mid=(l+r+)>>;

         if(check(mid)) l=mid;

         else r=mid-;

     }

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

     else

     {

         for(int i=;i<=ans[now][];i++)

         {

             for(int j=;j<l;j++)

              printf("%c",c[j+ans[now][i]]-+'a');

             printf("\n");

         }

     }

 }

 int main()

 {

     while()

     {

         scanf("%d",&n);

         if(n==) break;

         init();

         get_sa(+n);

         get_he();

         ffind();

         printf("\n");

     }

     return ;

 }

 [POJ3294]

[POJ3294]

2016-07-18 11:04:28