字符串哈希

贡献者：有机物

　　字符串哈希和普通的哈希算法类似，字符串哈希是把一个很长的字符串变成一个整数，这样的好处是：如果想比较两个很长的字符串是否相等时，普通算法是遍历一遍整个字符串，如果其中一个字符串的字符和另一个字符串的字符不等，则两个字符串不一样。时间复杂度为 $O(N)$。而用字符串哈希的话可以直接比较两个字符串的哈希值是否相同，时间复杂度为 $O(1)$。下面介绍一种哈希方式可以把任意一个字符串变成一个非负整数，并且哈希冲突的概率几乎为 $0$。

　　哈希函数通常设计为：取一固定值 $P$，把字符串看作 $P$ 进制数，并分配一个大于 $0$ 的数值，代表每种字符。再取一固定值 $M$，求出 $P$ 进制数转换十进制的数对 $M$ 的余数，作为这个字符串的哈希值。一般来说，$p$ 取 $131$ 或 $13331$ 时出现冲突的概率几乎为 $0$，通常 $M$ 取 $2^{64}$，可以直接用 unsigned long long 这个变量类型存储哈希值，溢出时就相当于对 $2^{64}$ 取模。

　　举个例子：先把一个字符串 $\text{abcfea}$ 变成 $p$ 进制数，将字符 $a \sim z$ 映射成 $1 \sim 26$，所以原来的字符串就变成了：$(123651)_p$，转化为十进制就为：

\begin{equation} 1 \times p^5 + 2 \times p^4 + 3 \times p^3 + 6 \times p^2 + 5 \times p^1 + 1 \times p^0~, \end{equation}

相加得出答案：$39175337388$ 作为这个字符串的哈希值。

　　一般在做哈希的时候，存储哈希的数组会存字符串的前缀哈希值，比如用 h 数组存储字符串的哈希值，h[1] = a 的哈希值，h[2] = ab 的哈希值，这样以此类推。那怎么算前缀哈希值呢？比如我们已经知道了 hash(S) 的哈希值，那么在字符串 $S$ 后面添加一个字符串 $C$ 构成的新字符串的哈希值为：hash(S+C) = hash(S) * P + value[C]。乘 $P$ 就相当在 $P$ 进制下于左移一位，加 value[C] 就是字符串 $C$ 所分配的数值。

　　举个例子：比如我们知道 hash(abc)，想算 hash(abcd) 的话就是：hash(abc) * P + value[d]。

　　 S = "abc"，C = "d"

　　 $S$ 表示为 $P$ 进制数：$(123)_p$，$C$ 表示为 $P$ 进制数：$(4)_p$

　　 hash(S) = $1 \times p^2 + 2 \times p^1 + 3 \times p^0=17426 $

　　 hash(S+C) = $1 \times p^2 *p + 2 \times p^1*p + 3 \times p^0*p + 4 = 1 \times p^3 + 2 \times p ^ 2 + 3 \times p^1 + 4=2282810 $

　　 hash(abc)=17426，hash(abc) * 131+4 = 17426 * 4 + 4 = 2282810。

　　这样就有了第一个公式：

　　 hash(S+C) = hash(S) * P + value[C]

　　我们还可以通过前面算的所以前缀哈希值，即 h 数组，可以 $O(1)$ 的时间复杂度算出任意一个子串的哈希值。

　　如果我们已知字符串 S 的 Hash 值为 H(S)，字符串 S+T 的 Hash 值为 H(S+T), 则：H(T) = H(S + T) - H(S) * p^length(T)

　　举个例子：我们知道 hash(abcd) 的哈希值为 $2282810$，hash(ab) 的哈希值为 $133$，想求 hash(cd) 的哈希值就为： $2282810 - 133\ \times 131^2 = 2282810 - 133 \times 11716 = 2282810 - 2282413 = 397$。

　　为了方便，可以开一个数组 $p$ 来记录 p^length(T)，即 $p$ 的多少次方。

　　具体的看一道例题：

　　给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l1,r1,l2,r2$，请你判断 $[l1,r1]$ 和 $[l2,r2]$ 这两个区间所包含的字符串子串是否完全相同。

　　因为字符串中包含大小写英文字母和数字，所以我们把字符的 value 值设置为字符的 ASCII 码。

const int N = 1e5 + 10, P = 131;

typedef unsigned long long ULL;

ULL n, m, p[N], h[N];
char str[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1]; // 推出来的公式 2
}

int main()
{
    cin >> n >> m >> str + 1;
    
    p[0] = 1;  // p 的 0 次方为 1
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + (int)str[i];  // 推出来的公式 1， value 为字符的 ASCII
        p[i] = p[i - 1] * P;
    }
    
    // for (int i = 1; i <= n; i ++ )
    // {
    //     cout << p[i] << ' '; // p 的多少次方
    //     cout << h[i] << ' '; // 前缀哈希值
    // }
    // cout << endl;
    
    while (m -- )
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (get(l1, r1) == get(l2, r2) ? "Yes\n" : "No\n");
    }
    
    return 0;
}