【数据结构】字符串哈希

先看一下这道题：

用substr肯定超时，这道题可以用字符串哈希。

大致思路是：

把字符串映射成一个P进制的数来表示，例如字符串ABCD，那么可以令A=1，B=2，C=3，D=4，...，那么$hash(ABCD)=1*P^{3}+2*P^{2}+3*P^{1}+4*P^{0}$。

这道题可以首先初始化一个h数组，h[i]存储前i个字符串的hash值，例如：$h[1] = hash(A), h[2] = hash(AB), h[3]=hash(ABC), h[4]=hash(ABCD)$，那么字串BC的hash值=$h[3]-h[1]*P^{2}$，其实如果P=10，即十进制就相当于BC=ABC-A*100=123-100=23。

那么有一个问题就是如果字符串太长势必会导致它的hash值非常大，造成溢出，所以一般需要对一个值进行取模例如$2^{64}$，P通常取131，那么h数组可以定义成unsigned long long，溢出就相当于取模。

那么这道题的代码：

#include <iostream>

using namespace std;

int main()
{
    int n, m;
    unsigned long long h[100005], P = 131, p[100005]; // p[2] = P^2

    char str[100005];
    
    cin >> n >> m;
    cin >> str + 1;
    
    h[0] = 0;
    p[0] = 1;
    for(int i = 1; i <= n ; i ++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    
    while(m--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if((h[b] - h[a - 1] * p[b - a + 1]) == (h[d] - h[c - 1] * p[d - c + 1]))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    
}