字符串哈希代码
/*
* Project: 11_哈希表
* File Created:Sunday, January 17th 2021, 6:15:10 pm
* Author: Bug-Free
* Problem:AcWing 841. 字符串哈希
*/
#include <algorithm>
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
cin >> n >> m;
cin >> (str + 1);
p[0] = 1; // p^0 =1;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
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;
}
这里get里面的l - 1啥意思,一直不理解
其实
__int128long long 也行。其实int也行。。
大佬 在p进制里算这个数是 最高次幂不应该是p^(字符长度-1)吗 那为什么在预处理p的幂的时候要处理到p^(字符长度) 呢
一个字节不是8位嘛?那usignend l l 不应该可以2的128次幂嘛
无符号长型变量是用于数字存储的扩展大小变量,可存储32位(4字节)。与标准长整型不同,无符号长整型不会存储负数,使它们的范围从0到4,294,967,295(2^32-1)。
就是我查的long long 是八个字节,那加了unsign不就是*2了吗,初学者见谅哈qwq
https://stackoverflow.com/questions/5836329/how-many-bytes-is-unsigned-long-long
数字在计算机中用二进制存储,8 个字节有64位,但 long long 中第一位代表符号,1为负,0为正,因此这一位不能用来存数值,所以 long long 的范围是 $±2^{63}−1$ ,至于为什么要减1,就像用十进制存一位最多存到 9 一样。如果不要符号位,那么 unsigned long long 就可以用 64 位存,范围是 $2^{64}−1$ 。所以 unsigned long long 的绝对值严格来说不等于 long long 的两倍。