洛谷 P2463 [SDOI2008]Sandy的卡片 解题报告

时间：2022-05-10 16:27:34

P2463 [SDOI2008]Sandy的卡片

题意

给\(n(\le 1000)\)串，定义两个串相等为“长度相同，且一个串每个数加某个数与另一个串完全相同”，求所有串的最长公共子串，每个串长\(\le 101\)，值域\(\in [0,1864]\)

先差分一下，然后连在一起中间加分隔符建sa

然后dp一下，要用到lcp，复杂度\(O(nm^2+n\log n)\)

Code:

#include <cstdio>

#include <algorithm>

using std::min;

using std::max;

const int N=2e5;

int tax[N],sa[N],Rank[N],sec[N],n,m=2000,hei[N],st[N][18],Log[N];

int s[N],dp[N],L[110],R[110],num,mi[1100];

void Rsort()

{

	for(int i=1;i<=m;i++) tax[i]=0;

	for(int i=1;i<=n;i++) ++tax[Rank[i]];

	for(int i=1;i<=m;i++) tax[i]+=tax[i-1];

	for(int i=n;i;i--) sa[tax[Rank[sec[i]]]--]=sec[i];

}

bool cmp(int x,int y,int l){return sec[x]==sec[y]&&sec[x+l]==sec[y+l];}

void SuffixSort()

{

	for(int i=1;i<=n;i++) Rank[i]=s[i],sec[i]=i;

	Rsort();

	for(int w=1,p=0;p<n;m=p,w<<=1)

	{

		p=0;for(int i=n-w+1;i<=n;i++) sec[++p]=i;

		for(int i=1;i<=n;i++) if(sa[i]>w) sec[++p]=sa[i]-w;

		Rsort(),std::swap(Rank,sec),Rank[sa[1]]=p=1;

		for(int i=2;i<=n;i++) Rank[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;

	}

	//h[i]>=h[i-1]-1;

	for(int i=1,p=0,j;i<=n;hei[Rank[i]]=p,i++)

		for(p=p?p-1:p,j=sa[Rank[i]-1];s[i+p]==s[j+p];++p);

	Log[0]=-1;for(int i=1;i<=n;i++) st[i][0]=hei[i],Log[i]=Log[i>>1]+1;

	for(int j=1;j<=17;j++)

	{

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

			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);

	}

}

int lcp(int x,int y)

{

    if(x>y) return lcp(y,x);

    ++x;

	int d=Log[y+1-x];

	return min(st[x][d],st[y-(1<<d)+1][d]);

}

int main()

{

	scanf("%d",&num);

	for(int las,i=1;i<=num;i++)

	{

		scanf("%d",mi+i);

		--mi[i];

		L[i]=n+1;

		scanf("%d",&las);

		for(int bee,j=1;j<=mi[i];j++)

        {

            scanf("%d",&bee);

            s[++n]=bee-las+m;

            las=bee;

        }

        R[i]=n++;

	}

	m=4000,--n;

	for(int i=2;i<=num;i++) s[L[i]-1]=++m;

	SuffixSort();

	for(int i=1;i<=mi[1];i++) dp[i]=mi[1]+1-i;

	for(int i=2;i<=num;i++)

	{

		for(int j=L[i];j<=R[i];j++)

			for(int k=L[i-1];k<=R[i-1];k++)

				dp[j]=max(dp[j],min(dp[k],lcp(Rank[k],Rank[j])));

	}

	int ans=0;

	for(int i=L[num];i<=R[num];i++) ans=max(ans,dp[i]);

	printf("%d\n",ans+1);

	return 0;

}

2019.2.1

相关文章