自动搬运

查看原文

来自洛谷，原作者为

	grass8cow 已淡坑

搬运于2025-08-24 22:30:02，当前版本为作者最后更新于2021-05-01 17:39:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一个显然的dp：

令 $f_i$ 表示文本串前 $i$ 位已经覆盖完的最小代价。

若 $s[i,j]$ 是个模式串，显然有 $f_j=\min(f_k+1)(i-1\le k<j)$

多模式串匹配，考虑 AC 自动机。

对于所有模式串建出 ACAS ，易对文本串进行匹配。

由转移方程，求 $f_j$ 时显然想让 $i$ 最小，模式串就尽量大。匹配到的那个点到 $fail$ 根上的所有点里，那些表示某模式串末尾的，就能和它的 $len$ 取 $\max$ 。这个不用每次求，直接预处理实现。

把这个 $i$ 求出来，$dp$ 就随便拿个数据结构实现即可。我用的是反向 $ST$ 表。

my code:

#include<bits/stdc++.h>
using namespace std;
int n;char c[300010],cc[300010];
int ch[300010][26],cn=1,len[300010],fail[300010];
queue<int>q;
void build(){
	for(int i=0;i<26;i++)if(ch[1][i])fail[ch[1][i]]=1,q.push(ch[1][i]);else ch[1][i]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		len[u]=max(len[u],len[fail[u]]);
		for(int i=0;i<26;i++)if(ch[u][i])
			fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
		else ch[u][i]=ch[fail[u]][i];
	}
}
int dp[300010][20];
int ask(int l,int r){
	if(l>r)return 1e9+7;
	int k=log2(r-l+1);
	return min(dp[r][k],dp[l+(1<<k)-1][k]);
}
int main(){
	scanf("%d%s",&n,cc+1);
	for(int i=0;i<n;i++){
		scanf("%s",c);int l=strlen(c),u=1;
		for(int j=0;j<l;j++){
			if(!ch[u][c[j]-'a'])ch[u][c[j]-'a']=++cn;
			u=ch[u][c[j]-'a'];
		}
		len[u]=max(len[u],l);
	}
	build();int le=strlen(cc+1),u=1;
	memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
	for(int i=1;i<=le;i++){
		u=ch[u][cc[i]-'a'];
		dp[i][0]=ask(i-len[u],i-1)+1;
		for(int j=1;j<20;j++){
			if(i-(1<<j)+1<0)break;
			dp[i][j]=min(dp[i][j-1],dp[i-(1<<j-1)][j-1]);
		}
	}
	return printf("%d",dp[le][0]>1e9?-1:dp[le][0]),0;
}