2025.5.17 字符串hash

 输入长度为n的字符串 有m个询问每次有四个参数，l1,r1,l2,r2。求每次[l1,r1]和[l2,r2]所包含的子串是否相等，时的话输出yes，不是no

#include <iostream>
//有很多问题可以用字符串hash 并不一定要用kmp
//字符串hash是一种特殊的hash:字符串前缀hash法
//求hash的时候预处理出来所有前缀的hash 如何定义某一个前缀的hash值:将字符串看成一个p进制的数，每一位字母就表示p进制数字的每一位数字
//转化为数字的话比较大，那么就将前缀代表的数字来mod上一个较小的数字q,那么前缀就被映射到0~q-1上了//注意:不能把某一个字母映射成0
//hash字符串时假定我们人品足够好，不存在冲突(直接不考虑),有个经验值,当p=131/13331，q=pow(2,64)时，在99%的情况下都不会发生冲突
//这样大费周章的算出前缀hash值有什么好处，可以用它计算出任意字串的hash值//给定长度为n的字符串 m次询问，每次有l1,r1,l2,r2,表示一次询问的两个区间，如果两个字串完全相同输出yes，反之
//*p=131/13331，q=pow(2,64)*    这时我们发现q是2^64，当用unsigned long long存储hash值时如果值溢出就会自然mod上2^64，免除手动mod
using namespace std;typedef unsigned long long ull;const int N = 100010, P = 131;int n, m;
char str[N];
ull h[N], p[N];   //p数组表示的是预处理的p的多少次方 p是power(指数)的缩写ull get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}int main()
{cin >> n >> m >> str + 1;      //注意这里一定是str+1p[0] = 1;for (int i = 1; i <= n; i++)   //预处理p和h{p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + str[i];}while (m--){int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;if (get(l1, r1) == get(l2, r2))cout << "yes" << endl;else cout << "no" << endl;}return 0;
}