【后缀数组】【二分答案】【差分】poj1743 Musical Theme

差分消除加减一个值得影响，貌似r二分上界要设成(n-2)/2？为啥？

sa求不可重叠最长重复子串

给定一个字符串，求最长重复子串，这两个子串不能重叠。
算法分析：
这题比上一题稍复杂一点。先二分答案，把题目变成判定性问题：判断是否
存在两个长度为 k 的子串是相同的，且不重叠。解决这个问题的关键还是利用
height 数组。把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都
不小于 k。

容易看出，有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然
后对于每组后缀，只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于
k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为
O(nlogn)。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define N 20001

#define INF 2147483647

int n,s[N],tong[N],sa[N],t[N],t2[N],rank[N],lcp[N];

bool check(int x)

{

	int maxsa=sa[0],minsa=sa[0];

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

	  {

	  	if(lcp[i]<x||i==n)

	  	  {

	  	  	if(maxsa-minsa>=x) return 1;

	  	  	maxsa=minsa=sa[i];

	  	  }

	  	else if(lcp[i]>=x)

	  	  {

	  	  	maxsa=max(maxsa,sa[i]);

	  	  	minsa=min(minsa,sa[i]);

	  	  }

	  }

	return 0;

}

bool cmp(int *y,int i,int k)

{

	return ((y[sa[i-1]]==y[sa[i]])&&((sa[i-1]+k>=n?-1:y[sa[i-1]+k])==(sa[i]+k>=n?-1:y[sa[i]+k])));

}

void build_sa(int range)

{

	int *x=t,*y=t2;

	memset(tong,0,sizeof(int)*range);

	for(int i=0;i<n;++i) tong[x[i]=s[i]]++;

	for(int i=1;i<range;++i) tong[i]+=tong[i-1];

	for(int i=n-1;i>=0;--i) sa[--tong[x[i]]]=i;

	for(int k=1;k<=n;k<<=1)

	  {

	  	int p=0;

	  	for(int i=n-k;i<n;++i) y[p++]=i;

	  	for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;

	  	memset(tong,0,sizeof(int)*range);

	  	for(int i=0;i<n;++i) tong[x[y[i]]]++;

	  	for(int i=1;i<range;++i) tong[i]+=tong[i-1];

	  	for(int i=n-1;i>=0;--i) sa[--tong[x[y[i]]]]=y[i];

	  	swap(x,y); p=1; x[sa[0]]=0;

	  	for(int i=1;i<n;++i) x[sa[i]]=cmp(y,i,k)?p-1:p++;

	  	if(p>=n) break;

	  	range=p;

	  }

}

void get_lcp()

{

	int k=0;

	for(int i=0;i<n;++i) rank[sa[i]]=i;

	for(int i=0;i<n;++i) if(rank[i])

	  {

	  	if(k) --k;

	  	int j=sa[rank[i]-1];

	  	while(s[i+k]==s[j+k]) ++k;

	  	lcp[rank[i]]=k;

	  }

}

int t3[N];

int main()

{

	while(1)

	  {

	  	scanf("%d",&n);

	  	if(!n) break;

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

		  {

		  	scanf("%d",&t3[i]);

		  	s[i]=t3[i]-t3[i-1]+89;

		  }

	  	build_sa(200);

	  	get_lcp();

	  	int l=0,r=(n-2>>1);

	  	while(r>l)

	  	  {

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

	  	  	if(check(mid)) l=mid;

	  	  	else r=mid-1;

	  	  }

	  	printf("%d\n",l>=4?l+1:0);

	  }

	return 0;

}

巴特西

【后缀数组】【二分答案】【差分】poj1743 Musical Theme

最新文章

热门文章