博客

分析：

比较裸的后缀自动机题。

先求出每个前缀能匹配的最大后缀。然后二分答案做DP

f

[

i

]

=

m

a

x

{

f

[

i

−

1

]

,

f

[

j

]

+

i

−

j

}

(

j

∈

[

i

−

m

a

x

l

e

n

i

,

i

−

k

]

)

f[i]=max\{f[i-1],f[j]+i-j\}(j\in [i-maxlen_i,i-k])

f[i]=max{f[i−1],f[j]+i−j}(j∈[i−maxleni​,i−k])

m

a

x

l

e

n

i

maxlen_i

maxleni​即以i为结尾的前缀的最大匹配后缀长度。

很显然j的取值右端点是单增的，稍微证明一下也会发现左端点也是单增的。

然后就可以单调队列优化DP了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1100010
#define MAXS 3
using namespace std;
struct node{
	int len;
	node *ch[MAXS];
	node *fail;	
}SuA[MAXN],*last,*ncnt,*rt;	
void Insert(int c){
	node *p=last;
	node *np=++ncnt;
	np->len=p->len+1;
	last=np;
	while(p&&!p->ch[c])
		p->ch[c]=np,p=p->fail;
	if(!p)
		np->fail=rt;
	else{
		node *q=p->ch[c];
		if(q->len==p->len+1)
			np->fail=q;
		else{
			node *nq=++ncnt;
			*nq=*q;
			nq->len=p->len+1;
			np->fail=q->fail=nq;
			while(p&&p->ch[c]==q)
				p->ch[c]=nq,p=p->fail;
		}
	}
}
int res[MAXN];
void match(char s[],int N){
	node *now=rt;
	int len=0;
	for(int i=0;i<N;i++){
		int c=s[i]-'0';
		if(now->ch[c]){
			len++;
			now=now->ch[c];	
		}
		else{
			while(now&&!now->ch[c])
				now=now->fail;
			if(!now)
				now=rt,len=0;
			else
				len=now->len+1,now=now->ch[c];
		}
		res[i]=len;
	}
}
int q[MAXN],tl,hd,f[MAXN];
int n,m;
bool check(int k,int len){
	hd=1;tl=0;
	for(int i=1;i<=len;i++){
		f[i]=f[i-1];
		if(i-k>=0){
			int add=i-k;
			while(hd<=tl&&f[q[tl]]-q[tl]<f[add]-add)
				tl--;
			q[++tl]=add;
		}
		while(hd<=tl&&q[hd]<i-res[i-1])
			hd++;
		if(hd<=tl)
			f[i]=max(f[i],f[q[hd]]-q[hd]+i);
	}
	return f[len]*10>=len*9;
}
void init(){
	rt=ncnt=last=SuA;	
}
char str[MAXN];
int main(){
	init();
	SF("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		SF("%s",str);
		int len=strlen(str);
		for(int j=0;j<len;j++)
			Insert(str[j]-'0');
		Insert(2);	
	}
	for(int i=0;i<n;i++){
		SF("%s",str);
		int len=strlen(str);
		match(str,len);	
		int l=1,r=len,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(mid,len)){
				ans=mid;
				l=mid+1;
			}
			else
				r=mid-1;
		}
		PF("%d\n",ans);
	}
}