AcWing 841. 字符串哈希 关于h==r的边界问题
原题链接
简单
作者:
说什么不可能
,
2020-09-23 17:58:52
,
所有人可见
,
阅读 327
关于get函数中左边界为l-1而不是l的理解
如果左边界取l 当左右相等的时候 无法取到l=r时字母的哈希值
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10;
const int P = 131;
int m,n;
char s[N];
ULL h[N];
ULL p[N];
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1]; // l==r? 是无法求出r处字符的哈希值的
}
int main()
{
scanf("%d%d%s",&m, &n, s+1);
p[0] = 1;
for(int i = 1; i <= m; i++)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
}
while(n --)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1,r1) == get(l2,r2))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
建议修改Markdown&删去不重要内容
终于有人吐槽这一点了_(:з」∠)_,我想吐槽有些题解很久了,都不知道用markdown的么
第一次使用 抱歉 会学习改进的。
加油www
++