BZOJ 2806 Luogu P4022 [CTSC2012]Cheat (广义后缀自动机、DP、二分、单调队列)

题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=2806

(luogu) https://www.luogu.org/problemnew/show/P4022

题解:对“作文库”中的串建广义SAM。(感觉加个#拼在一起直接SAM也行啊，只是常数大了点，但是大家都写的广义SAM我也就跟着写广义SAM了233333)

询问时二分\(L\), 变成求最少几个位置不匹配。然后DP方程是\(dp[i]=\min(dp[i-1]+1,\min_{i-match[i]\le j\le i-L} dp[j])\). 其中\(match[j]\)表示以\(j\)结尾最长能匹配的子串长度，用后缀自动机求出。单调队列优化即可。

应该a[i]-=96我写成a[i]-=48; dp完了之后不更新ans; 二分分反……我是有多无脑

注意一个问题是，由于这里有\(mid\)的限制，只有\(\le i-mid\)的位置才能被放进单调队列, 不可以一上来就把\(0\)放进去!

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1.1e6;

const int S = 2;

int son[(N<<1)+3][S+1];

int fa[(N<<1)+3];

int len[(N<<1)+3];

char a[N+3];

char b[N+3];

int match[N+3];

int dp[N+3];

int dq[N+3];

int n,m,siz,rtn,lstpos;

void initSAM()

{

	siz = rtn = lstpos = 1;

}

void insertchar(char ch)

{

	int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1;

	for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}

	if(!p) {fa[np] = rtn;}

	else

	{

		int q = son[p][ch];

		if(len[q]==len[p]+1) {fa[np] = q;}

		else

		{

			siz++; int nq = siz; len[nq] = len[p]+1;

			memcpy(son[nq],son[q],sizeof(son[q]));

			fa[nq] = fa[q]; fa[np] = fa[q] = nq;

			for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}

		}

	}

}

int main()

{

	initSAM();

	scanf("%d%d",&n,&m);

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

	{

		lstpos = rtn;

		scanf("%s",a+1); int lena = strlen(a+1);

		for(int j=1; j<=lena; j++) {insertchar(a[j]-48);}

	}

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

	{

		scanf("%s",a+1); int lena = strlen(a+1);

		for(int j=1; j<=lena; j++) {a[j]-=48;}

		int u = rtn,cur = 0;

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

		{

			while(u && son[u][a[j]]==0) {u = fa[u]; cur = len[u];}

			if(son[u][a[j]]) {u = son[u][a[j]]; cur++;}

			else {u = rtn; cur = 0;}

			match[j] = cur;

		}

		int left = 0,right = lena,mid,ans;

		while(left<right)

		{

			mid = (left+right+1)>>1;

			dp[0] = 0; int head = 1,tail = 0;

			if(mid<=1) {tail++; dq[tail] = 0;}

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

			{

				dp[j] = dp[j-1]+1;

				while(head<=tail && dq[head]<j-match[j]) {dq[head] = 0; head++;}

				if(head<=tail)

				{

					dp[j] = min(dp[j],dp[dq[head]]);

				}

				if(j-mid+1>=0)

				{

					while(head<=tail && dp[dq[tail]]>=dp[j-mid+1]) {dq[tail] = 0; tail--;}

					tail++; dq[tail] = j-mid+1;

				}

			}

			ans = dp[lena];

			if(ans*10<=lena) {left = mid;}

			else {right = mid-1;}

		}

		printf("%d\n",left);

	}

	return 0;

}

巴特西

BZOJ 2806 Luogu P4022 [CTSC2012]Cheat (广义后缀自动机、DP、二分、单调队列)

代码

最新文章

热门文章