自动搬运

查看原文

来自洛谷，原作者为

	MoonCake2011 有朋自远方来，板砖呼，左手呼完右手呼，呼不S再呼||题目很少，很快就做完了。微笑着做完，才会胜利。||原 Libingyue2011||J:400->360->280 S:265->258

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

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

以下是正文

来个简单的 Hash 做法吧。

打死不用 KMP。

Part 1,about Hash

先给出初始化的代码。

cin>>n>>m>>q;
cin>>a>>b;
a=" "+a,b=" "+b;
power[0]=1;
//前缀 Hash 值进制数选的是 131，Hash 可以把一个前缀字符串压成整数
//预处理前缀 Hash 值，用 ull 自然溢出取模，其实 Hash 的冲突概率很小啦
//power计算是计算进制位权的，用于配合前缀 Hash 值计算每一个字串的 Hash 值
for(int i=1;i<=n;i++) ha[i]=ha[i-1]*131+a[i],power[i]=power[i-1]*131;
for(int i=1;i<=m;i++) hb[i]=hb[i-1]*131+b[i],power[i]=power[i-1]*131; 

接下来需要计算前缀 Hash 值。

$s$ 为 string 字符串。

可以表示为 $H(s_r)-H(s_{l-1})\times 131^{r-l+1}$。

为什么，要乘以个 $131^{r-l+1}$。

因为要在 $s_{l-1}$ 后补 $r-l+1$ 个空字符才能于 $s_r$ 相减。

因为 $r$ 位字符串于 $l-1$ 位字符串是不一样的。

unsigned long long geta(int l,int r){
	return ha[r]-ha[l-1]*power[r-l+1];
}
unsigned long long getb(int l,int r){
	return hb[r]-hb[l-1]*power[r-l+1];
}

接着，我们就可以 $O(1)$ 比较两个子串了。

Part 2,Multiply Search

倍增查找，在这里比二分好用。

我们先枚举每个后缀字串的开头 $b$。

去枚举匹配结尾的下一个位置 $e$。

如 $a[b,e)$ 的 Hash 值等于 $b[1,e-b+1)$ 那么就匹配上了。

匹配值取值 $[0,1]$。

又发现,匹配值满足单调性。

直接上倍增。

这里上倍增的原因是可以设置两个指针 $p,q$。

一个在 $a$ 上面指，一个在 $b$ 上面指。

最后建立一个桶，去统计 $q-1$ 就行了。

代码。

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
string a,b;
unsigned long long ha[200010],hb[200010],power[200010];
unsigned long long geta(int l,int r){
	return ha[r]-ha[l-1]*power[r-l+1];
}
unsigned long long getb(int l,int r){
	return hb[r]-hb[l-1]*power[r-l+1];
}
int buc[2000100];
int main() {
	cin>>n>>m>>q;
	cin>>a>>b;
	a=" "+a,b=" "+b;
	power[0]=1;
	for(int i=1;i<=n;i++) ha[i]=ha[i-1]*131+a[i],power[i]=power[i-1]*131;
	for(int i=1;i<=m;i++) hb[i]=hb[i-1]*131+b[i],power[i]=power[i-1]*131; 
	for(int i=1;i<=n;i++){
		int p=i,q=1;//两个指针
		for(int i=30;i>=0;i--){
			if(p+(1<<i)-1>n || q+(1<<i)-1>m) continue;
			if(geta(p,p+(1<<i)-1)==getb(q,q+(1<<i)-1)) p+=(1<<i),q+=(1<<i);//Hash 值倍增
		}
		buc[q-1]++;//统计
	}
	while(q--){//求解
		int x;
		cin>>x;
		cout<<buc[x]<<"\n";
	}
	return 0;
}