【后缀自动机+二分答案+DP】熟悉的文章

动态规划DP, 字符串

传送门：CodeVS1753

思路：

  • 将作文库建成SAM；
  • 然后把每个待判定的串放进去跑，求出每一位上与作文库的LCS；
  • 二分答案；
    • 进行dp，$f_i$表示到第i位最长的匹配字数，len表示二分的答案；
    • $f_i=max{f_{i-1},max{f_j+i-j\ |\ i-lcs_i\leqslant j\leqslant i-len}}$
    • 由于$i-lcs_i,i-len$均单调递增，套一个单调队列优化即可。

注意：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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 3000000
int n,m,cnt,p,np,q,nq,c[N][3],stt[N],fa[N],f[N],qq[N],match[N];
char s[N];
void extend(int w){
	p=np; stt[np=++cnt]=stt[p]+1;
	for (;p && !c[p][w];p=fa[p]) c[p][w]=np;
	if (!p) fa[np]=1;
	else{
		if (stt[q=c[p][w]]==stt[p]+1) fa[np]=q;
		else{
			stt[nq=++cnt]=stt[p]+1;
			memcpy(c[nq],c[q],sizeof c[q]);
			fa[nq]=fa[q]; fa[q]=fa[np]=nq;
			for (;c[p][w]==q;p=fa[p]) c[p][w]=nq;
		}
	}
}
bool check(char s[],int L){
	int tt=1,ww=0,len=strlen(s+1);
	for (int i=1;i<=len;i++){
		f[i]=f[i-1];
		if (i-L<0) continue;
		while (tt<=ww && f[qq[ww]]-qq[ww]<f[i-L]-(i-L)) ww--;
		qq[++ww]=i-L;
		while (tt<=ww && qq[tt]<i-match[i]) tt++;
		if (tt<=ww) f[i]=max(f[i],i+f[qq[tt]]-qq[tt]);
	}
	if (f[len]*10>=len*9) return 1; return 0;
}
void solve(char s[]){
	int xb=1,len=strlen(s+1),tmp=0;
	for (int i=1;i<=len;i++){
		int w=s[i]-'0';
		for (;xb && !c[xb][w];xb=fa[xb]);
		if (!xb){xb=1; tmp=match[i]=0;}
		else{tmp=min(tmp,stt[xb])+1; xb=c[xb][w]; match[i]=tmp;}
	}
	int l=0,r=len,ans=0;
	while (l<=r){
		int mid=(l+r)>>1;
		if (check(s,mid)){ans=mid; l=mid+1;} else r=mid-1;
	}
	printf("%d\n",ans);
}
int main(){
	scanf("%d%d",&n,&m);
	cnt=1;
	for (int i=1;i<=m;i++){
		scanf("%s",s+1); int len=strlen(s+1); 
		np=1;for (int j=1;j<=len;j++) extend(s[j]-'0');
	}
	for (int i=1;i<=n;i++){scanf("%s",s+1); solve(s);}
	
	return 0;
}