首页 > 代码库 > 【BZOJ2806】[Ctsc2012]Cheat 广义后缀自动机+二分+单调队列优化DP

【BZOJ2806】[Ctsc2012]Cheat 广义后缀自动机+二分+单调队列优化DP

2024-10-13 02:41:39   218人阅读

【BZOJ2806】[Ctsc2012]Cheat

Description

技术分享

技术分享

Input

第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库
的行数
接下来M行的01串，表示标准作文库
接下来N行的01串，表示N篇作文

Output

N行，每行一个整数，表示这篇作文的Lo 值。

Sample Input

1 2
10110
000001110
1011001100

Sample Output

4

HINT

输入文件不超过1100000字节

注意：题目有改动,可识别的长度不小于90%即可，而不是大于90%

题解：显然答案是可二分的。但是二分之前，我们还需要知道字符串中每个位置往前最多能匹配多少，由于是多个文本串，所以我们要用广义SAM。

这其实是另一道spoj的题（不过我没做），其实做法也不难。我们将目标串在SAM上跑一遍，如果在某个节点失配了，即ch[x][a]=0，那么我们就让x沿着parent指针已知向上跳，知道匹配上为止，然后令sum=mx[x]+1。如果没有失配，则sum++。（注意，ch[x][a]指向的点的mx不一定=mx[x]+1，实际上，那个点的mx=mx[x在parent树上的某个子孙]+1）

然后我们设f[i]表示位置i能往前匹配的最长长度，那么有如下DP方程：

$f[i]=max(f[i-1],f[j]+i-j)|i-sm[i]\le j \le i-L_0$

显然我们用单调队列维护f[j]-j的最大值就行了。

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,tot,len;const int maxn=2200010;int pre[maxn],ch[maxn][2],mx[maxn],sm[maxn],f[maxn],q[maxn];char str[maxn];int extend(int x,int p){	int np=++tot;	mx[np]=mx[p]+1;	for(;p&&!ch[p][x];p=pre[p])	ch[p][x]=np;	if(!p)	pre[np]=1;	else	{		int q=ch[p][x];		if(mx[q]==mx[p]+1)	pre[np]=q;		else		{			int nq=++tot;			pre[nq]=pre[q],pre[np]=pre[q]=nq,mx[nq]=mx[p]+1;			memcpy(ch[nq],ch[q],sizeof(ch[q]));			for(;p&&ch[p][x]==q;p=pre[p])	ch[p][x]=nq;		}	}	return np;}void match(){	int i,u,a,sum=0;	for(u=i=1;i<=len;i++)	{		a=str[i]-‘0‘;		if(ch[u][a])	sum++,u=ch[u][a];		else		{			for(;u&&!ch[u][a];u=pre[u]);			if(!u)	sum=0,u=1;			else	sum=mx[u]+1,u=ch[u][a];		}		sm[i]=sum;	}}bool solve(int sta){	int i,j,h=1,t=0;	for(i=0;i<=len;i++)	f[i]=0;	for(i=sta-1;i<=len;i++)	{		while(h<=t&&q[h]<i-sm[i])	h++;		f[i]=f[i-1];		if(sm[i]>=sta)	f[i]=max(f[i],f[q[h]]-q[h]+i);		j=i-sta+1;		while(h<=t&&f[q[t]]-q[t]<=f[j]-j)	t--;		q[++t]=j;	}	return f[len]*10>=len*9;}int main(){	scanf("%d%d",&n,&m);	int i,j,a,b,l,r,mid;	for(tot=i=1;i<=m;i++)	{		scanf("%s",str),a=strlen(str);		for(b=1,j=0;j<a;j++)	b=extend(str[j]-‘0‘,b);	}	for(i=1;i<=n;i++)	{		scanf("%s",str+1),len=strlen(str)-1;		match();		l=1,r=len+1;		while(l<r)		{			mid=l+r>>1;			if(solve(mid))	l=mid+1;			else	r=mid;		}		printf("%d\n",l-1);	}	return 0;}

 

【BZOJ2806】[Ctsc2012]Cheat 广义后缀自动机+二分+单调队列优化DP


联系
我们