题解：P10479 匹配统计
MoonCake2011
·
·
题解
来个简单的 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 值。
可以表示为 $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$ 位字符串是不一样的。
```cpp
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$ 就行了。
代码。
```cpp
#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;
}
```