自动搬运

查看原文

来自洛谷，原作者为

	夜临 **

搬运于2025-08-24 22:01:46，当前版本为作者最后更新于2020-09-07 21:42:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为是最优解就来写题解了（滑稽）

从数据大小上分析，这道题的 $n$ 的大小比较大，但是图案的大小和图案个数 $m$ 都比较小，较普遍的算法是使用AC自动机进行字符匹配，但是这里我们使用哈希，在加上优化后不仅空间比AC自动机小很多，而且在普遍的测试点中时间非常快，所有测试点时间之和只有$657ms$。

先考虑比较朴素的匹配，即将 $m$ 个小字符串进行哈希，再在大字符串上 $O(n)$ 进行匹配，然后通过差分来实现对能铺的位置的覆盖。

但是显然这样的时间复杂度是 $O(n\times m)$ ，所以我们要对算法进行优化。

首先一个较明显的思路是对字符串的开头第一个字母进行分类，先将$m$个哈希值预处理出来，再按照首字母分别装到不同的数组中，在每次询问的时候只要询问需要的首字母的数组即可，那么这样的时间复杂度度就能减少26倍。

这样就已经是第二优解了，但是这并不是最快的，我们还可以再每个大字符串的字符匹配时，从长度最大的字符串开始匹配，这样当我们匹配成功时，剩下的部分就没有必要在匹配了。

于是一个简单的哈希加差分加剪枝就能飞快地A掉这道黑题。 ٩(๑❛ᴗ❛๑)۶

下面是我自己的代码。

ps:我使用的是对最后一个字符进行分类，这样能防止被卡，使代码更快。

#include<bits/stdc++.h>
#define un unsigned long long
using namespace std;
const int N=3e5+5;
struct z{
	int Len;
	un Has;
} g[30][5005];//将哈希值与长度装在结构体中方便排序和调用
int n,m,Len,cnt[30],L[N];
un f[N],num[N],p;
char a[N],s[5005];
bool cmp(z a,z b){
	return a.Len>b.Len;
}
int main(){
	scanf("%d%s",&n,&a);
	num[0]=1;
	for(int i=0;i<n;i++)f[i]=f[i-1]*233+a[i],num[i+1]=num[i]*233;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%s",&s);
		Len=strlen(s);
		int mb=s[Len-1]-'a';//按照尾字母分类
		p=0;
		for(int j=0;j<Len;j++)p=p*233+s[j];
		g[mb][++cnt[mb]]=(z){Len,p};
	}
	for(int i=0;i<26;i++)sort(g[i]+1,g[i]+cnt[i]+1,cmp);
	for(int i=0;i<n;i++){
		int mb=a[i]-'a';//按照尾字母进行查询
		for(int j=1;j<=cnt[mb];j++){
			Len=g[mb][j].Len;
			if(i<Len-1)continue;
			if(f[i]-f[i-Len]*num[Len]==g[mb][j].Has){
				L[i-Len+1]++,L[i+1]--;//对覆盖区域进行差分
				break;//剩下的都是比当前字符串短的，就算匹配成功对答案也没有贡献，可以直接break
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(i>0)L[i]+=L[i-1];
		if(L[i]==0)ans++;
	}
	cout<<ans;
}