复习一下我们这里的字符串哈希
C++ 代码
//在这里我们重新学习一下这里的字符串哈希的函数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int P = 131;//这里的N一般取值为131
const int N = 100010;
ULL p[N];//用来存入我们的指数
ULL s[N];//用来存入我们的前缀和
char str[N];
int n,m;
//将其进行初始化
void init()
{
p[0]=1;
s[0]=0;
for(int i=1;i<=n;i++)
{
p[i]=p[i-1]*P;
s[i]=s[i-1]*P+str[i];
}
}
ULL get(int l,int r)
{
return s[r]-s[l-1]*p[r-l+1];
}
int main()
{
scanf("%d%d%s", &n, &m,str+1);
init();
while (m -- )
{
int l1,r1,l2,r2;
cin >> l1>>r1>>l2>>r2;
if(get(l1,r1)==get(l2,r2))
{
puts("Yes");
}
else
{
puts("No");
}
}
return 0;
}