字符串哈希

AcWing 841. 字符串哈希
本题链接：AcWing 841. 字符串哈希

 

本题解析
预处理字符串的前缀哈希：

str = "ABCDEFG"
h[0] = 0;
h[1] = "A"的hash
h[2] = "AB"的hash
h[3] = "ABC"的hash
......


如何求字符串的hash：

把每一位当成p进制的数
例如"ABCD"
我们对应来看可以是
 A B C D
(1 2 3 4)p
那么对于"ABCD"而言的十进制表达为：
1 * P³ + 2 * p² + 3 * p + 4

我们说过，哈希其实就是映射，我们求得的数字可能会非常的大，所以我们可以取模

(1 * P³ + 2 * p² + 3 * p + 4) mol Q

这里我们给出一些规定：
不能把一个字母的hash值映射成0
我们一般把p取值为131或13331
Q取值为2^64

通过这种处理方法我们就可以算出来任意子区间的hash
 

#include 
#include 
#include "源.h"
 
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];
 
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
 
int main()
{
    cin >> n >> m;
    cin >> str + 1;
    //scanf("%d%d", &n, &m);
 
 
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
        cout<<"p["<"]" << p[i] << endl;
    }
 
    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;
}