字符串哈希

贡献者： 有机物

　　 字符串哈希和普通的哈希算法类似，字符串哈希是把一个很长的字符串变成一个整数，这样的好处是：如果想比较两个很长的字符串是否相等时，普通算法是遍历一遍整个字符串，如果其中一个字符串的字符和另一个字符串的字符不等，则两个字符串不一样。时间复杂度为 $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$，转化为十进制就为：

　　 一般在做哈希的时候，存储哈希的数组会存字符串的前缀哈希值，比如用 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\ast p+2\times p^1\ast p+3\times p^0\ast 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;
}