AcWing 841. 字符串哈希
原题链接
简单
作者:
Chandler丶
,
2024-03-04 20:57:03
,
所有人可见
,
阅读 18
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define ll long long
// 字符串哈希:使用场景:判断两个字符串的子串是否相同
const int N = 100010, P = 131;//这里p = 131是经验值,来减少哈希冲突
typedef unsigned long long ULL;//这里用 ULL 来替代 unsigned long long ,减少输入
ULL h[N],p[N];
int n , m;
char str[N];
ULL get(int l,int r)
{
return h[r]- h[l-1] *p[r - l +1];
}
int main() {
scanf("%d%d%s",&n, &m, str+1);
p[0] = 1;//初始化 p[0]
for(int i = 1; i <= n; i++)
{
p[i] = p[i-1] * P;
h[i] = h[i - 1] * P + str[i];
//相当于前一个位置的哈希值 乘以 P 再加上当前位置的字符对应的数值 (ASCII码)
}
while(m -- )
{
int l1 , r1 , l2, r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1) == get(l2,r2)) puts("Yes");
else puts("No");
}
}