子串查找（哈希模板 下标从1开始）
题目描述：
(这是一道模板题)
给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母。
A中不同位置出现的 B 可重叠。
输入格式:
输入共两行，分别是字符串 A 和字符串 B。
输出格式:
输出一个整数，表示 B 在 A 中的出现次数。
样例输入:
zyzyzyz
zyz
样例输出:
3
数据范围与提示:
1<=A,B的长度<=10^6，A,B仅包含大小写字母
AC代码详解
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;//定义无符号长整型
//无符号长整型的输出格式为%llu,取值范围为0~2^64-1
//无符号数自然溢出的结果也为正整数
const ULL b = 1e9+7;//b取1e9+7的时候几乎不可能发生冲突，可以记住
const int N = 1000005;
char s1[N],s2[N];//s1为主串
int ans;//ans是我们要求的s2在s1中出现的次数
//pow数组储存的是b的多少次方，sum数组储存的是主串的前i项的哈希值 ，s储存的是模拟串的哈希值
ULL power[N],sum[N],s;
ULL get(int l,int r){
return sum[r]-sum[l-1]*power[r-l+1];
}
int main()
{
int i;
scanf("%s%s",s1+1,s2+1); //输入字符串的下标从1开始
power[0]=1;
//预处理一下b的n次方，即打表
for (i=1; i<1000000; i++)
power[i]=power[i-1]*b; //b的1次方，2次方...n次方,让它自然溢出
ULL m=strlen(s1+1), n=strlen(s2+1);//求一下s1和s2字符串的长度
sum[0]=0;
for (i=1; i<=m; i++) /*主串的哈希值*/
//主串的哈希值必须要用数组存起来，因为主串的每一段都要与模拟串的哈希值做对比
sum[i]=sum[i-1]*b+s1[i];//将主串的每一段都转换成b进制数
for (i=1; i<=n; i++)
s=s*b+s2[i]; /*s定义成全局变量（s的初始值为0），s为模拟串的哈希值*/
for (i=1; i+n-1<=m; i++) //i只需要<=m-n即可，因为我们的主串最多只有m位，我们主串的哈希值最多只计算到sum[m]
//因为字符串是从下标1开始的，所以这里从i=1开始
if (get(i,i+n-1)==s)
ans++;
printf("%d\n",ans);
return 0;
}字符串哈希（下标从0开始）
(题目链接)[https://www.acwing.com/problem/content/843/]
#include<bits/stdc++.h>
using namespace std;
using ULL = unsigned long long;
//typedef unsigned long long ULL;
const int N = 100005;
ULL p[N],h[N];
string s;
int P=131;//13331也可
// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或 13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL get(int l,int r){
//if(l == 0) return h[r];
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
int n,k,l1,l2,r1,r2;
string a,b,s;
cin>>n>>k;
cin>>s;
p[0]=1;
for(int i=0;i<n;i++){ //相比下标从0开始略有不同
p[i+1] = p[i]*P;
if(i==0)
h[i]=s[i];
else
h[i] = h[i-1]*P +s[i]; //前缀和求整个字符串的哈希值
}
while(k--){
cin>>l1>>r1>>l2>>r2;
if(get(l1-1,r1-1)==get(l2-1,r2-1)) //因为题目要其字符串下标从1开始，所以这里要减一
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
