Beyond the Void
BYVoid
pku 1743 Musical Theme
本文正體字版由OpenCC轉換

把原序列相鄰每項做差,然後問題就轉化成了求一個串的最長不重疊重複子串,且兩個子串相距至少一位,可以用後綴數組做。

首先求出後綴數組和Height數組,Height[i]=LCP(SA[i],SA[i-1])。接下來二分答案A,判定A是否爲可行解。判斷方法是找出在Height數組中找出連續的一段Height[i..j],使得i<=k<=j均滿足Height[k]>=A,並且i-1<=k1,k2<=j中,要有Max{SA[k1]} - Min{SA[k2]} >= A + 1(距離相差至少1),這時A是可行的。

後綴數組的分組思想十分重要,這道題就是一個經典應用,還應用到了求最長公共子串(LCS)問題。

/*
 * Problem: pku1743 Musical Theme (USACO 28)
 * Author: Guo Jiabao
 * Time: 2009.4.17 18:45
 * State: Solved
 * Memo: 後綴數組 最長重複子串
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=20011,INF=0x7FFFFFFF;
using namespace std;
struct SufficArray
{
	struct RadixElement
	{
		int id,k[2];
	}RE[MAXN],RT[MAXN],*R1,*R2;
	int N,A[MAXN],SA[MAXN],Rank[MAXN],Height[MAXN],C[MAXN];
	void RadixSort()
	{
		int i,y;
		for (y=1,R1=RE,R2=RT;y>=0;y--)
		{
			memset(C,0,sizeof(C));
			for (i=1;i<=N;i++) C[ R1[i].k[y] ]++;
			for (i=1;i<MAXN;i++) C[i]+=C[i-1];
			for (i=N;i>=1;i--) R2[ C[ R1[i].k[y] ]-- ]=R1[i];
			R1=RT,R2=RE;
		}
		for (i=1;i<=N;i++)
		{
			Rank[RE[i].id]=Rank[RE[i-1].id];
			if ( RE[i].k[0]!=RE[i-1].k[0] || RE[i].k[1]!=RE[i-1].k[1] )
				Rank[RE[i].id]++;
		}
	}
	void CalcSA()
	{
		int i,k;
		Rank[RE[0].id=0]=0;RE[0].k[0]=-1;
		for (i=1;i<=N;i++)
			RE[i].id=i,RE[i].k[0]=A[i],RE[i].k[1]=0;
		RadixSort();
		for (k=1;k+1<=N;k*=2)
		{
			for (i=1;i<=N;i++)
				RE[i].id=i,RE[i].k[0]=Rank[i],RE[i].k[1]=i+k<=N?Rank[i+k]:0;
			RadixSort();
		}
		for (i=1;i<=N;i++)
			SA[Rank[i]]=i;
	}
	void CalcHeight()
	{
		int i,k,h=0;
		for (i=1;i<=N;i++)
		{
			if (Rank[i]==1)
				h=0;
			else
			{
				k=SA[Rank[i]-1];
				if (h) h--;
				for (;A[i+h]==A[k+h];h++);
			}
			Height[Rank[i]]=h;
		}
	}
}SA;
int N,Ans;
bool check(int A)
{
	int i,j,Min,Max;
	for (i=1;i<=SA.N;i++)
	{
		if (SA.Height[i]>=A)
		{
			Min=Max=SA.SA[i-1];
			for (j=i;j<=SA.N && SA.Height[j]>=A;j++)
			{
				if (SA.SA[j]<Min)
					Min = SA.SA[j];
				if (SA.SA[j]>Max)
					Max = SA.SA[j];
			}
			j--;
			if (Max-Min>A)
				return true;
			i=j;
		}
	}
	return false;
}
void solve()
{
	int a,b,m;
	SA.CalcSA();
	SA.CalcHeight();
	a=0;b=SA.N;
	while (a+1<b)
	{
		m=(a+b)/2;
		if (check(m))
			a=m;
		else
			b=m-1;
	}
	if (check(b))
		a=b;
	Ans=a+1;
	if (Ans<5) Ans=0;
}
void init()
{
	int i,c,d,md=INF;
	memset(&SA,0,sizeof(SA));
	d=-100;
	for (i=1;i<=N;i++)
	{
		scanf("%d",&c);
		SA.A[++SA.N]=c-d;
		if (c-d<md)
			md=c-d;
		d=c;
	}
	md--;
	for (i=1;i<=N;i++)
		SA.A[i]-=md;
}
int main()
{
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
	while (scanf("%d",&N),N)
	{
		init();
		solve();
		printf("%dn",Ans);
	}
	return 0;
}

上次修改時間 2017-02-03

相關日誌