P4022 [CTSC2012]熟悉的文章

发表于 | 评论数： | 阅读次数：
本文字数： 4.1k | 阅读时长 ≈ 4 分钟

P4022 [CTSC2012]熟悉的文章

传送门

洛谷

题目描述

阿米巴是小强的好朋友。

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

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：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 值比其他同学的明显要大。请你帮他验证一下。

输入输出格式

输入格式：

输入文件 cheat.in 第一行是两个整数 N, M，表示待检查的作文数量，和小强的标准作文库的行数。

接下来是 M 行的 01 串，表示标准作文库。

接下来是 N 行的 01 串，表示 N 篇作文。

输出格式：

输出文件 cheat.out 包含 N 行，每一行包含一个整数，表示该篇作文的 L 0 值。

输入输出样例

输入样例#1：

1 2
10110
000001110
1011001100

输出样例#1：

4

说明

对于 30%的测试数据，输入文件的长度不超过 1000 字节。

对于 50%的测试数据，输入文件的长度不超过 61000 字节。

对于 80%的测试数据，输入文件的长度不超过 250000 字节。

对于 100%的测试数据，输入文件的长度不超过 1100000 字节。

分析

$0pts：$不打或打炸。
看到求最小的最大值，想到二分。
证明一波：
很明显，对于大的可行的串，它的小的子串一定也可行(即，对于一个可行的L,小于它的L一定也可行)，反之不一定成立，满足单调性，所以可以二分。
那么怎么$check$呢？？？
想到DP。
我们设$f_i$表示以$i$位置结尾时题意要求的最大值。
很容易写出转移方程如下：

其中，$len_i$表示符合题意要求的分割的最大值，即以$i$结尾的可以被匹配的01串的最大值。
直接搞，$60pts$到手。
但转念想想，正解(如果也是用这个DP方程的话)不可能直接暴力转移，不然就满分了，不会才$60pts$。
如果想要通过本题的话，复杂度应该是在$O(nlogn)$左右。
那么转移应该做到$O(1)$才行。
想想把$O(n)$的DP转移优化为$O(1)$的方法就那么几种。
再发现两个边界($i-len_i$,$i-L$)中第一个边界肯定是单调不降的，第二个边界是单调上升的，很容易理解和证明，这里省去证明。
于是想到单调队列优化DP。
稍微化一下式子就行了。
DP处理完了。
想一想$len_i$怎么求，发现这个东西在广义$SAM$上跑一下就行了。
另外，在打代码的时候注意一下循环语句的执行顺序，我就在把while改for的时候爆炸了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1000010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,m,sl,cnt=1,las,Q[maxn],f[maxn],match[maxn],len[maxn<<1],fa[maxn<<1],ch[maxn<<1][2];
char str[maxn];
void add(int cc)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][cc];p=fa[p])ch[p][cc]=np;
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][cc];
		if(len[q]==len[p]+1)fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			fa[nq]=fa[q];
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][cc]==q;p=fa[p])ch[p][cc]=nq;
		}
	}
}
void Match()
{
	int p=1,l=0,c;
	for(int i=1;i<=sl;i++)
	{
		c=str[i]-'0';
		if(ch[p][c])p=ch[p][c],l+=1;
		else
		{
			for(;p&&!ch[p][c];p=fa[p]);
			if(p)l=len[p]+1,p=ch[p][c];
			else p=1,l=0;
		}
		match[i]=l;
	}
}
bool check(int L)
{
	int h=1,t=0;
	for(int i=1;i<=L-1;i++)f[i]=0;
	for(int i=L;i<=sl;i++)
	{
		f[i]=f[i-1];
		while(h<=t&&f[Q[t]]-Q[t]<f[i-L]-(i-L))t-=1;
		Q[++t]=i-L;
		while(h<=t&&Q[h]<i-match[i])h+=1;
		if(h<=t)f[i]=max(f[i],f[Q[h]]+i-Q[h]);
	}
	return f[sl]*10>=sl*9;
}
int main()
{
	read(n,m);
	for(int i=1;i<=m;i++)
	{
		las=1;
		scanf("%s",str+1);
		sl=strlen(str+1);
		for(int j=1;j<=sl;j++)add(str[j]-'0');
	}
	for(int tot=1;tot<=n;tot++)
	{
		scanf("%s",str+1);
		sl=strlen(str+1);
		Match();
		int l=0,r=sl,ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(check(mid))ans=mid,l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
    return 0;
}