题目描述

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标\(L_0\).小强首先将作文转化成一个01串。之后，小强搜集了各路名家的文章，同样分别转化成01串后，整理出一个包含了\(M\)个01串的“ 标准作文库 ”。

小强认为：如果一个01串长度不少于\(L\)且在“标准作文库”中的某个串里出现过（即，它是“标准作文库”的某个串的一个连续子串），那么它是“熟悉”的。对于一篇作文（一个01串）\(A\)，如果能够把\(A\)分割成若干段子串，其中“ 熟悉 ”的子串的长度总和不少于\(A\)总长度的\(90%\)，那么称\(A\)是 “ 熟悉的文章 ”。\(L_0\)是能够让\(A\)成为“熟悉的文章”的所有\(L\)的最大值（如果不存在这样的\(L\)，那么规定 \(L_0=0\)）。

举个例子：

小强的作文库里包含了如下\(2\)个字符串：

10110

000001110

有一篇待考察的作文是：

1011001100

小强计算出这篇作文\(L\)的最大值是\(4\)，因为待考察的作文可以视作'10110'+'0110'+'0'，其中'10110'和'0110'被判定为“熟悉”的。而当\(L=5\)或是更大的时候，不存在符合题意的分割方法。所以，这篇作文的\(L_0=4\)。小强认为阿米巴作文的\(L_0\)值比其他同学的明显要大。请你帮他验证一下。

sol

显然\(L_0\)是可二分的吧。

那么我们二分出一个\(L\)，对原序列做一遍\(check\)

发现这个玩意儿很像一个序列\(dp\)？

设\(f_i\)表示前\(i\)个位置能够匹配的最大长度。那么转移有：

\[f_i=max(f_j+i-j),i-j>=L且s[j+1..i]能够匹配
\]

这个是强制\(i\)在匹配里的，那么令\(f[i]=max(f[i],f[i-1])\)就可以满足设定了。

我们设\(pp[i]\)表示匹配到\(i\)位置时的最长匹配长度，那么\(s[j+1..i]\)能够匹配就当且仅当\(j>=i-pp[i]\)。显然\(i-pp[i]\)是单调的，所以我们可以维护一个\(i\)递增\(f[i]-i\)递减的单调队列，每次取队首元素更新\(dp\)值。

至于\(i-j>=L\)的限制，我们只要在计算\(f[i]\)之前，把\(i-L\)插入到单调队列里面去就行了。

复杂度变成了优秀的\(O(n\log{n})\)

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 2e6+5;

int n,m,l,last=1,tot=1,tr[N][2],fa[N],len[N],pp[N],q[N],dp[N];

char s[N];

void extend(int c)

{

	int v=last,u=++tot;last=u;

	len[u]=len[v]+1;

	while (v&&!tr[v][c]) tr[v][c]=u,v=fa[v];

	if (!v) fa[u]=1;

	else{

		int x=tr[v][c];

		if (len[x]==len[v]+1) fa[u]=x;

		else{

			int y=++tot;

			memcpy(tr[y],tr[x],sizeof(tr[y]));

			fa[y]=fa[x];fa[x]=fa[u]=y;len[y]=len[v]+1;

			while (v&&tr[v][c]==x) tr[v][c]=y,v=fa[v];

		}

	}

}

bool check(int mid)

{

	int hd=1,tl=0;

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

	{

		dp[i]=dp[i-1];

		if (i<mid) continue;

		while (hd<=tl&&dp[q[tl]]-q[tl]<=dp[i-mid]-i+mid) --tl;

		q[++tl]=i-mid;

		while (hd<=tl&&q[hd]<i-pp[i]) ++hd;

		if (hd<=tl) dp[i]=max(dp[i],dp[q[hd]]+i-q[hd]);

	}

	return dp[l]*10>=l*9;

}

int main()

{

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

	while (m--)

	{

		scanf("%s",s+1);l=strlen(s+1);

		last=1;

		for (int i=1;i<=l;++i) extend(s[i]-'0');

	}

	while (n--)

	{

		scanf("%s",s+1);l=strlen(s+1);

		for (int i=1,now=1,cnt=0;i<=l;++i)

		{

			int c=s[i]-'0';

			if (tr[now][c]) ++cnt,now=tr[now][c];

			else{

				while (now&&!tr[now][c]) now=fa[now];

				if (!now) cnt=0,now=1;

				else cnt=len[now]+1,now=tr[now][c];

			}

			pp[i]=cnt;

		}

		int L=0,R=l;

		while (L<R)

		{

			int mid=L+R+1>>1;

			if (check(mid)) L=mid;

			else R=mid-1;

		}

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

	}

	return 0;

}

巴特西

[BZOJ2806][CTSC2012]熟悉的文章(Cheat)

题目描述

sol

code

最新文章

热门文章