洛谷 4022.「CTSC2012」熟悉的文章

也不是一道特别难的题(

建广义 SAM,对询问串的每个前缀找最长的后缀满足其为标准作文库中的子串,设这个长度为 \(l_i\)

考虑二分 \(L\),DP 判断。
注意到 \(i - l_i\) 不降,单调队列优化 DP 即可。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1.1e6;
int n,m,q;
int L[N + 5];
char s[N + 5],t[N + 5];
int l,r,mid,ans;
namespace SAM
{
struct node
{
int ch[2];
int fa,len;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
int c[N + 5],a[(N << 1) + 5];
inline void insert(int x)
{
if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
{
las = sam[las].ch[x];
return ;
}
int cur = las,p = ++tot,flag = 0,nxt;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
cur == las && (flag = 1),nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
las = flag ? nxt : p;
}
}
int f[N + 5];
int check()
{
static int q[N + 5],head,tail;
head = 1,tail = 0,memset(f,0,sizeof(int) * mid);
for(register int i = mid;i <= m;++i)
{
for(;head <= tail && f[i - mid] - i + mid > f[q[tail]] - q[tail];--tail);
q[++tail] = i - mid;
for(;head <= tail && q[head] < i - L[i];++head);
f[i] = f[i - 1],head <= tail && (f[i] = max(f[i],f[q[head]] + i - q[head]));
}
return f[m] >= m * 0.9;
}
int main()
{
scanf("%d%d",&q,&n);
for(register int i = 1;i <= n;++i)
{
scanf("%s",s),SAM::las = 1;
for(char *c = s;*c;SAM::insert(*c++ ^ '0'));
}
for(;q;--q)
{
scanf("%s",t + 1),m = strlen(t + 1);
for(register int i = 1,x,p = 1,len = 0;i <= m;++i)
{
x = t[i] ^ '0';
if(SAM::sam[p].ch[x])
p = SAM::sam[p].ch[x],++len;
else
{
for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
!p ? (p = 1,len = 0) : (len = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
}
L[i] = len;
}
for(l = 1,r = m,ans = 0;l <= r;)
mid = l + r >> 1,check() ? (ans = mid,l = mid + 1) : (r = mid - 1);
printf("%d\n",ans);
}
}