题目描述：

这是一道模板题。

给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母。
A中不同位置出现的 B 可重叠。

输入格式:

输入共两行，分别是字符串 A 和字符串 B。

输出格式:

输出一个整数，表示 B 在 A 中的出现次数。

样例输入:

zyzyzyz
zyz

样例输出:

3

数据范围与提示:

1<=A,B的长度<=10^6，A,B仅包含大小写字母

模板题，hash函数思路：

我们选取两个合适的互质常数b，h（b小于h），假设字符串$C=c_1{c}_2...c_m$,那么$H(C)=(c_1{b}^{m-1}+c_2{b}^{m-2}+...+c_m{b}^0)modh$这里把b看作基数,相当于看作是b进制数,b取值应适宜.
而我们经过预处理$b_1...b_n$和哈希值后,判断子串就为主串一段字符与匹配字符的哈希值是否相等,即$$H(C^{\prime })=H(C,k+n)-H(C,k)\ast b^n$$

预处理$b^n$(注意开unsigned long long)

for(int i=1;i<=1000000;i++){bb[i]=bb[i-1]*b;}

主串哈希值

for(int i=1;i<=len1;i++){ahash[i]=ahash[i-1]*b+(unsigned long long)(s1[i]-'A'+1);}

模板代码

#include<bits/stdc++.h>
using namespace std;
unsigned long long bb[1000099],ahash[1119999],ss;
int n,b=11,ans=0;
char a;
char s1[1099999],ansa[1000999];
int main(){scanf("%s%s",s1+1,ansa+1);bb[0]=1;for(int i=1;i<=1000000;i++){bb[i]=bb[i-1]*b;}int len1=strlen(s1+1),len2=strlen(ansa+1);ahash[0]=0;for(int i=1;i<=len1;i++){ahash[i]=ahash[i-1]*b+(unsigned long long)(s1[i]-'A'+1);}for(int i=1;i<=len2;i++){ss=ss*b+(unsigned long long)(ansa[i]-'A'+1);}for(int i=0;i<=len1-len2;i++){if(ss==ahash[i+len2]-ahash[i]*bb[len2])ans++;}cout<<ans;return 0;
}