本文主要是介绍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;elser=mid;}if(r<=1){puts("?");continue;}print(r-1);}return 0;
}
这篇关于poj 3294（Life Forms） 2分+ 后缀数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
