算法简介

字符串哈希是将字符串映射为数字的算法，它通常用来解决快速判断两个字符串是否相等的问题。

时间复杂度

\(O(n + m)\)

实现原理

1. 构造原理

字符串哈希运用了进制的思想，将字符串变为 p 进制的数字。

如：""

可以映射为：\((X_1 * P^{n-1} + X_2 * P^{n-2} + \cdots + X^{n-1} + X_n * P^{0}) \mod Q\)

该过程中需要注意的点是：

1. 字符不能映射为 0 ，否则会出现 A，AA，AAA 字符串全部映射为 0 的情况。
2. P 一般取值 131 或 13331 时冲突概率最小。
3. Q 一般取值 \(2^{64}\)，等同于 unsigned long long 的数据范围，可以利用 C++ 的溢出机制自动取模。

2. 区间哈希值

这里用数组 h[i] 表示当前字符串前 i 个字符组成的字符串的哈希值

例如："ABCDEFGHIJK"
h[1] = "A" 的哈希值
h[2] = "AB" 的哈希值
h[3] = "ABC" 的哈希值
...
h[11] = "ABCDEFGHIJK" 的哈希值

那么如何求得 [l,r] 区间内的哈希值呢？

给出公式：\(h[l,r] = h[r] - h[l-1] * p^{r-l+1}\)

假设有字符串 ABCD：

则有：

\(h[1] = A * p^0\)
\(h[2] = A * p^1 + B * p^0\)
\(h[3] = A * p^2 + B * p^1 + C * p^0\)
\(h[4] = A * p^3 + B * p^2 + C * p^1 + D * p^0\)

若要求 BC 的哈希值，那么根据公式则有：

\(h[2,3] = h[3] - h[1] * p^2\)

则有

\(h[3] - h[1] * p^2 = (A * p^2 + B * p^1 + C * p^0) - (A * p^0) * p^2 = B * p^1 + C * p^0 = "BC"\)

或者可以通俗理解，copy 一个大佬的解释：

算法实例

1. 题目描述

https://www.acwing.com/problem/content/description/843/

2. AC代码

#include <bits/stdc++.h>

typedef unsigned long long ULL;

const int N = 100010, P = 131; // P = 13331

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()
{
    std::cin >> n >> m;
    std::cin >> str + 1;
    
    p[0] = 1;
    for (int i = 1 ; i <= n ; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    
    while(m -- )
    {
        int l1,r1,l2,r2;
        std::cin >> l1 >> r1 >> l2 >> r2;
        
        if(get(l1,r1) == get(l2,r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

参考

https://www.acwing.com/solution/content/24738/