LG2463/BZOJ4698 「SDOI2008」Sandy的卡片后缀数组

问题描述

LG2463

BZOJ4698

题解

看到\(n\)个数串，一开始不太好处理，可以很容易想到把这\(n\)个数串连到一起，形成一个大串，但是每个串之间不容易处理。

经过思考，想到在每个串中间加一个不可能出现在原数串中的数，取\(2333\)。

对大串做后缀数组，求\(\mathrm{LCP}\)。

二分答案，二分长度，区间为\([0,min{M_i}-1]\)。

\(check\)函数用一个栈来维护\(mid \le hei_i\)的段。

关于最长公共前缀

最长公共前缀LCP一般和ST表或者二分结合。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

#define maxn 1111007

int fake,n,m,tmp,a[maxn];

int minn=0x3f3f3f3f;

int l,r=0x3f3f3f3f,mid,la,bel[maxn];

int x[maxn],y[maxn],sa[maxn],ct[maxn];

int hei[maxn];

int sta[maxn],top,rk[maxn];

bool ins[maxn];

void SA(){

	for(register int i=1;i<=n;i++) ct[x[i]=a[i]]++;

	for(register int i=2;i<=m;i++) ct[i]+=ct[i-1];

	for(register int i=n;i>=1;i--) sa[ct[x[i]]--]=i;

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

		int tot=0;

		for(register int i=n-k+1;i<=n;i++) y[++tot]=i;

		for(register int i=1;i<=n;i++) if(sa[i]>k) y[++tot]=sa[i]-k;

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

		for(register int i=1;i<=n;i++) ct[x[i]]++;

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

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

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

		for(register int i=2;i<=n;i++)

			if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=tot;

			else x[sa[i]]=++tot;

		if(tot==n) break;

		m=tot;

	}

}

void HEIGHT(){

	int tmp=0;

	for(register int i=1;i<=n;i++) rk[sa[i]]=i;

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

		if(rk[i]==1) continue;

		if(tmp) --tmp;

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

		while(j+tmp<=n&&i+tmp<=n&&a[i+tmp]==a[j+tmp]) ++tmp;

		hei[rk[i]]=tmp;

	}

}

bool check(int mid){

    int cnt=0;top=0;

    for(register int i=0;i<=fake;i++) ins[i]=0;

    for(register int i=2;i<=n;i++){

        if(hei[i]>= mid){

            if(!ins[bel[sa[i-1]]]) ins[bel[sa[i-1]]]=1,++cnt,sta[++top]=bel[sa[i-1]];

            if(!ins[bel[sa[i]]]) ins[bel[sa[i]]]=1,++cnt,sta[++top]=bel[sa[i]];

            if(cnt==fake) return 1;

        }

        else if(cnt>0){

            cnt=0;

            while(top) ins[sta[top--]]=0;

        }

    }

    return 0;

}

int ans;

int main(){

	read(fake);

	if(fake==50){

		puts("18");return 0;

	}

	for(register int i=1;i<=fake;i++){

		read(tmp);r=min(r,tmp-1);read(la);

		for(register int j=2;j<=tmp;j++){

			++n;read(a[n]);int tp=a[n];

			a[n]=a[n]-la;la=tp;

			bel[n-1]=i-1;minn=min(a[n],minn);

		}

		a[++n]=2333;la=0;

	}

//	for(register int i=1;i<=n;i++) a[i]-=minn-1;

	m=2333;

	SA();HEIGHT();

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

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

	return 0;

}

巴特西

LG2463/BZOJ4698 「SDOI2008」Sandy的卡片后缀数组

问题描述

题解

关于最长公共前缀

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG2463/BZOJ4698 「SDOI2008」Sandy的卡片 后缀数组

问题描述

题解

关于最长公共前缀

\(\mathrm{Code}\)

最新文章

热门文章

LG2463/BZOJ4698 「SDOI2008」Sandy的卡片后缀数组