字符串哈希：定义一种将字符串映射到一个整型哈希值的函数 $f(\cdot)$，我们希望这个函数可以方便地帮我们判断两个字符串是否相等。

字符串哈希函数

引例

将 $(1001)_2$ 这个二进制数转为十进制，按位拆分得到 $(1001)_2=1\cdot2^3+0\cdot2^2+0\cdot2^1+1\cdot2^0$

将 $(1234)_p$ 这个 $p$ 进制数转为十进制，按位拆分得到 $(1234)_p=1\cdot p^3+2\cdot p^2+3\cdot p^1+4\cdot p^0$

根据上面的例子，我们可以将字符串看为一个 $p$ 进制数，将它转为十进制便是它的哈希值。不过由于指数爆炸，字符串长度稍长一点，转换得到的数字大小就会变得非常巨大，因此我们还需要对结果取模。

定义

对于一个长度为 $l$ 的字符串 $s$ 来说，定义多项式哈希函数：

$$ f(s)=\sum_{i=1}^{l}s_i\times p^{l-i}\pmod m $$

这种多项式形式的哈希函数，字符串最左侧为多项式高位，最右侧为低位，相反的实现也是同样可行的，本文不讲另一种。

该哈希函数有两个参数，分别是底数 $p$ 和模数 $m$. 对于 $p$ 可以任意选择，对于 $m$ 需要选择一个素数，且至少要比最大的字符要大。

下面给出一些常用的选择，不过也要小心出题人把常用值给卡掉：

  • $p=131,13331,449,233$
  • $m=10^{9}+7,998244353,998244853,436522843,2^{64}$

其中 $2^{64}$ 便是自然溢出法了，选择 unsigned long long int 数据类型即可，范围 $[0,2^{64})$.

另外，因为字符串哈希处理冲突的开销较大，因此我们是不处理冲突的。所以用哈希处理字符串的题目，能不能过还是很玄学的。如果实在被卡掉了，可以试一下选择两个模数进行双哈希，这样的话哈希函数的值域就能扩大到两者之积，可以降低错误率。

代码

typedef long long ll;
constexpr ll P = 449, MOD = 436522843;

ll get_hash(string &s)
{
    ll res = 0;
    for (int i = 0; i < s.size(); i++)
        res = (res * P % MOD + s[i]) % MOD;
    return res;
}

子串哈希

原理

单次计算一个字符串的哈希值复杂度是 $O(n)$，其中 $n$ 为串长。如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。此时就要用到子串这个性质，减少重复计算。

字符串哈希具有类似前缀和的性质，如果预处理了该字符串的每个前缀子串的哈希值，那么就可以在 $O(1)$ 内得到该字符串所有子串的哈希值。不过和前缀和不同的是，并不能直接相减，而是要乘上一个“偏移量”再减。

具体来说，将前缀哈希值储存在 $h_i$ 中，$h_i$ 代表从第 $1$ 位到第 $i$ 位的前缀子串的哈希值。如果要求的子串左端点为第 $l$ 位，右端点为第 $r$ 位，则子串的哈希值 $h'$ 的计算公式：

$$ h'=h_r-p^{r-l+1}\cdot h_{l-1} $$

代码实现时，为了加快效率，将 $p$ 的幂次预处理好保存到数组内。

演示

我们用一个可视化的例子来演示：

$$ \begin{array}{r} (abcdef)_p & = & ap^5 & + & bp^4 & + & cp^3 & + & dp^2 & + & ep^1 & + & fp^0\\ (abc)_p & = & ap^2 & + & bp^1 & + & cp^0 & & & & & & \\ (abcde)_p & = & ap^4 & + & bp^3 & + & cp^2 & + & dp^1 & + & ep^0 & & \\ (de)_p & = & & & & & & & dp^1 & + & ep^0 & & \\ \end{array} $$

我们已知的是：

  • 第一行：$abcdef$ 的哈希值（仅作对比参考，实际算法是用不上的）
  • 第二行：$0\sim2$ 子串的哈希值 $h_2$.
  • 第三行：$0\sim4$ 子串的哈希值 $h_4$.

我们要求的是：

  • 第四行：$3\sim4$ 字串的哈希值。

通过比对我们可以发现：$(de)_p=h_4-p^2\cdot h_2$. 与上面式子的计算方式一致。

代码

struct StrHash
{
    int len, base, mod;
    vector<int> p, h;
    void init(const string &s, int base, int mod)
    {
        len = s.size();
        this->base = base;
        this->mod = mod;
        p.resize(len + 1);
        h.resize(len + 1);
        p[0] = 1;
        for (int i = 1; i <= len; i++)
            p[i] = p[i - 1] * base % mod;
        h[0] = s[0] % mod;
        for (int i = 1; i < len; i++)
            h[i] = (h[i - 1] * base % mod + s[i]) % mod;
    }
    int get(int l, int r)
    {
        if (l <= 0)
            return h[r];
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

允许 $k$ 次失配的字符串匹配

问题

给定长为 $n$ 的原串 $s$，以及长度为 $m$ 的模式串 $p$，要求查找原串中有多少子串与模式串匹配。$s'$ 与 $s$ 匹配，当且仅当 $s'$ 与 $s$ 长度相同，且最多有 $k$ 个位置字符不同。其中 $1\leq n,m\leq10^6$，$0\leq k\leq 5$.

解法

该问题无法使用 KMP 来解决，但是可用哈希 + 二分完成。思路如下：

枚举所有可能匹配的子串，假设现在枚举的子串为 $s'$，通过哈希 + 二分可以快速找到 $s'$ 与 $p$ 第一个不同的位置。之后不考虑这个失配位置及之前的部分，继续查找下一个失配位置。这样的过程最多发生 $k$ 次。

时间复杂度 $O(m+nk\log m)$

代码

$a$ 为模式串，$b$ 为子串，该函数返回子串是否能匹配上模式串。

/* 依赖上文的StrHash结构体 */
bool check(StrHash &a, StrHash &b, int toler)
{
    if (a.len < b.len) // make a >= b
        return check(b, a, toler);
    int la = a.len, lb = b.len;
    for (int i = 0; i <= la - lb; i++)
    {
        int err = 0, pos = 0;
        while (err <= toler && pos < lb)
        {
            int l = pos, r = lb - 1;
            while (l < r)
            {
                int mid = (l + r) / 2;
                if (a.get(i + pos, i + mid) == b.get(pos, mid))
                    l = mid + 1;
                else
                    r = mid;
            }
            if (a.get(i + pos, i + l) != b.get(pos, l))
                err++;
            pos = l + 1;
        }
        if (err <= toler)
            return true;
    }
    return false;
}

回文判定

回文判定的相关问题，也可以用字符串哈希来解决，核心思路就是预处理出原串的哈希和逆序串的哈希。

不过这种问题 manacher 算法往往也能完成，并且不会被卡。

比较典型的例题可以是：Codeforces Global Round 7 - D2