哈希表

哈希表说简单一点就是将一个大的集合映射到一个比较小的集合中。

一个很经典的例子 —— 字符串哈希。
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l_1,r_1,l_2,r_2，请你判断 [l_1,r_1] 和 [l_2,r_2] 这两个区间所包含的字符串子串是否完全相同。

当字符串的长度为10^9时，遍历显然就不便利了（谐音虽迟但到）。这个时候可以将字符串以一种特殊的方式变成数字编码，每一个数字编码只对应一个字符串。

一个具体的例子：如字符串ABCD，其中可以做如下映射：
A->1,B->2,C->3,D->4
继续将字符串看做一个P进制的数，则
ABCD=P^3+2P^2+3P^1+4P^0,这样该P进制数唯一对应ABCD字符串。

加上的前缀哈希的思想，现将前k位的哈希值算出来。
再回到上述问题：从 l 到 r 之间的字符串的哈希值如和得到？
类似于二进制的计算，如11010与110的差，要先将110转换为00110，将二者位数对齐，在进行计算，则我们可以得到以下公式：

具体代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

//字符前缀哈希法   h[k]表示前k个字符的哈希
//将字符串转换为P进制数  如ABCD=（1,2,3,4）p  则其哈希值为（1*p^3+2*p^2+3*p^1+4*1）_10
//在对哈希值取模 mod Q
typedef unsigned long long  ULL;

const int N = 100010, P = 131;        //P取131或13331  经验数值
int n, m;
char str[N];

ULL h[N], p[N];   

ULL getLR(int l, int r)    
{
    return h[r] - h[l - 1] * p[r - l + 1];         //计算l,r之间的哈希值
}

int main()
{
    cin >> n >> m >> str+1;
    p[0] = 1;
    for (int i = 1; i <= N; i++)
        p[i] = p[i - 1] * P,
        h[i] = h[i - 1] * P + str[i];              //计算前i位的哈希值

    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        if (getLR(l1, r1) == getLR(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}