答案≠题解

我想写个题解（题解区里的题解思路太干巴了），但我这个题是随手写的，没认真（因为太简单了）所以代码很乱，加注释也不知道怎么加，也没有模块化，胡成一团，怕大家不能看懂代码，所以就发个答案好了。

#include<iostream>
#define P 307
using namespace std;
int f[int(1e6)];
int main(){
	string a{"0zyzyzyz"},b{"0zyz"};
	cin>>a>>b;
	int lena=a.size(),lenb=b.size();
	a='0'+a;
	b='0'+b;
	f[1]=a[1];
	for(int i(2);i<=lena;i++)
		f[i]=f[i-1]*P+a[i];
	int fb(b[1]);
	for(int i(2);i<=lenb;i++)
		fb=fb*P+b[i];
	int p=1;
	for(int i(1);i<=lenb;i++)
		p*=P;
	int sum(0);
	for(int i(1);i<=lena-lenb+1;i++){
		int x=i;
		int y=x+lenb-1;
		if(fb==f[y]-f[x-1]*p)
			sum++;
	}
	cout<<sum;
}

里面有些很废物的东西，纯属写着玩（比如字符串的初始化），反正能过就行了。随便写的，写得跟坨屎一样。所以就不放题解处了。而且这个牌面很乱，也没有分模块，就是简单说一下，本题就下面几个事，莽就完了：

搞个a的前缀和哈希

把b的哈希搞出来

把p搞出来

推一下公式（不用背，我自己花了四十来秒就推出来了，真的不用背），给大家贴一下：

p是定值，就是上面说的把p搞出来，因为b的长度是固定的嘛。

最后累加一下，套公式，b的哈希值如果等于$S_{[x,y]}$就sum++，最后输出sum。

以上搞法时间复杂度：O(2lena+lenb)，也就是一次级，才$10^6$，肯定能过。