poj 3294（Life Forms） 二分+ 后缀数组

poj 3294（Life Forms） 2分+ 后缀数组

我曾用字符串hash写，但是超时了。只能用后最数组了。大致思路：用不同的符号吧字符串连接起来，构建后缀数组，然后2分答案，依次扫描后缀数组，看是否瞒住条件。

VIEW CODE

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<iostream>
#include<map>
#include<stack>
using namespace std;
const int mmax=210000;
int s[mmax];
int sa[mmax],t[mmax],t2[mmax],c[mmax],n;
void build_sa(int m)
{
    int i,*x=t,*y=t2;
    for(i=0;i<m;i++) c[i]=0;
    for(i=0;i<n;i++) c[ x[i]=s[i]]++;
    for(i=1;i<m;i++) c[i]+=c[i-1];
    for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<=n;k<<=1)
    {
        int p=0;
        for(i=n-k;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[y[i]]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if(p>=n) break;
        m=p;
    }
}
int rank[mmax],h[mmax];
void get_h()
{
    int i,j,k=0;
    for(i=0;i<n;i++) rank[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k) k--;
        if(rank[i])
        {
            j=sa[rank[i]-1];
            while(s[i+k]==s[j+k]) k++;
            h[rank[i]]=k;
        }
    }
}
char DNA[210][2100];
bool vis[210];
int id[mmax],N;
stack<int>q;
bool ok(int k)
{
    while(!q.empty())
        q.pop();
    memset(vis,0,sizeof vis);
    int cnt=1;
    vis[id[sa[0]]]=1;
    q.push(id[sa[0]]);
    for(int i=1;i<n;i++)
    {
        if(h[i]>=k)
        {
            if(!vis[id[sa[i]]])
            {
                cnt++;
                vis[id[sa[i]]]=1;
                q.push(id[sa[i]]);
            }
        }
        else
        {
            while(!q.empty())
            {
                int x=q.top();
                vis[x]=0;
                q.pop();
            }
            cnt=1;
            vis[id[sa[i]]]=1;
            q.push(id[sa[i]]);
        }
        if(2*cnt>N)
            return 1;
    }
    return 0;
}
void print(int k)
{
    while(!q.empty())
        q.pop();
    memset(vis,0,sizeof vis);
    int cnt=1;
    vis[id[sa[0]]]=1;
    q.push(id[sa[0]]);
    for(int i=1;i<n;i++)
    {
        if(h[i]>=k)
        {
            if(!vis[id[sa[i]]])
            {
                cnt++;
                vis[id[sa[i]]]=1;
                q.push(id[sa[i]]);
            }
        }
        else
        {
            if(2*cnt>N)
            {
                for(int j=0;j<k;j++)
                    printf("%c",s[sa[i-1]+j]);
                puts("");
            }
            while(!q.empty())
            {
                int x=q.top();
                vis[x]=0;
                q.pop();
            }
            cnt=1;
            vis[id[sa[i]]]=1;
            q.push(id[sa[i]]);
        }
    }
    if(2*cnt>N)
    {
        for(int j=0;j<k;j++)
            printf("%c",s[sa[n-1]+j]);
        puts("");
    }
}
int main()
{
    int len,l,r,ca=0;
    while(scanf("%d",&N)!=EOF && N)
    {
        if(ca)
            puts("");
        ca++;
        len=0;
        l=0,r=0;
        memset(id,0,sizeof id);
        memset(s,0,sizeof s);
        for(int i=1;i<=N;i++)
        {
            scanf("%s",DNA[i]);
            r=max(r,int(strlen(DNA[i])));
            for(int j=0;j<strlen(DNA[i]);j++)
                id[j+len]=i;
            for(int j=0;j<strlen(DNA[i]);j++)
                s[len++]=int(DNA[i][j]);
            s[len]='z'+i;
            id[len]=0;
            len++;
        }
        if(N==1)
        {
            printf("%s\n",DNA[1]);
            continue;
        }

        n=len;
        build_sa(230);
        get_h();
        r++;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(ok(mid))
                l=mid+1;
            else
                r=mid;
        }
        if(r<=1)
        {
            puts("?");
            continue;
        }
        print(r-1);
    }
    return 0;
}