2018.11.28 poj3294 Life Forms（后缀数组+双指针）

传送门

后缀数组经典题目。

我们先把所有的字符串都接在一起。

然后求出hththt数组和sasasa数组。

然后对于sasasa数组跑双指针统计答案。

如果双指针包括进去的属于不同字符串的数量达到了题目给出的限制我们就更新答案并不断右移左指针。

如果没有达到限制就一直右移右指针。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<algorithm>
#define ri register int
using namespace std;
const int N=2e5+5;
int rk[N],sa[N],sa2[N],ht[N],n,m,len[N],tt,tot[N],st[N][18],Log[N],idx[N];
char s[N],t[N];
vector<int>ans;
inline void Sort(){
	static int cnt[N];
	for(ri i=1;i<=m;++i)cnt[i]=0;
	for(ri i=1;i<=n;++i)++cnt[rk[i]];
	for(ri i=2;i<=m;++i)cnt[i]+=cnt[i-1];
	for(ri i=n;i;--i)sa[cnt[rk[sa2[i]]]--]=sa2[i];
}
inline void getsa(){
	for(ri i=1;i<=n;++i)rk[i]=(int)s[i],sa2[i]=i;
	m=122,Sort();
	for(ri w=1,p=0;m^n;w<<=1,p=0){
		for(ri i=n-w+1;i<=n;++i)sa2[++p]=i;
		for(ri i=1;i<=n;++i)if(sa[i]>w)sa2[++p]=sa[i]-w;
		Sort(),swap(sa2,rk),rk[sa[1]]=p=1;
		for(ri i=2;i<=n;++i)rk[sa[i]]=(sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+w]==sa2[sa[i-1]+w])?p:++p;
		m=p;
	}
	for(ri i=1,j,k=0;i<=n;ht[rk[i++]]=k)for(k?--k:k,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
	for(ri i=1;i<=n;++i)st[i][0]=ht[i];
	for(ri j=1;j<=17;++j)for(ri i=1;i+(1<<j)<=n;++i)st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
inline int rmq(int l,int r){return min(st[l][Log[r-l+1]],st[r-(1<<Log[r-l+1])+1][Log[r-l+1]]);}
inline bool check(int a,int b,int len){
	a=rk[a],b=rk[b];
	if(a>b)a^=b,b^=a,a^=b;
	return rmq(a+1,b)<len;
}
inline void solve(){
	ri sig=0,mxlen=0,lim=(tt>>1)+1,l=tt,r=tt-1;
	ans.clear();
	for(int i=1;i<=tt;++i)tot[i]=0;
	for(;;++l){
		while(sig<lim&&r<len[tt]){
			++r,++tot[idx[sa[r]]];
			if(tot[idx[sa[r]]]==1)++sig;
		}
		if(sig^lim)break;
		while(sig==lim){
			--tot[idx[sa[l]]];
			if(!tot[idx[sa[l]]]){
				ri tmp=rmq(l+1,r);
				if(tmp){
					if(tmp>mxlen)ans.clear(),ans.push_back(sa[l]),mxlen=tmp;
					else if(tmp==mxlen)ans.push_back(sa[l]);
				}
				--sig;
				break;
			}
			++l;
		}
	}
	if(!mxlen)puts("?");
	else for(ri i=0;i<ans.size();++i)if(!i||check(ans[i],ans[i-1],mxlen)){for(ri j=ans[i],k=1;k<=mxlen;++k,++j)cout<<s[j];puts("");}
}
int main(){
	freopen("lx.in","r",stdin);
	freopen("owon.out","w",stdout);
	Log[0]=-1;
	for(ri i=1;i<=200000;++i)Log[i]=Log[i>>1]+1;
	while(scanf("%d",&tt),n=0,tt){
		for(ri i=1;i<=tt;++i){
			scanf("%s",t),len[i]=strlen(t),s[++n]=(char)i;
			for(ri j=0;j<len[i];++j)s[++n]=t[j];
			++len[i],len[i]+=len[i-1];
		}
		for(ri i=1;i<=tt;++i)for(ri j=len[i-1]+1;j<=len[i];++j)idx[j]=i;
		getsa();
		solve(),puts("");
	}
	return 0;
}

巴特西

2018.11.28 poj3294 Life Forms（后缀数组+双指针）

最新文章

热门文章