字符串之字符串哈希

前言

Hash 函数有助于解决很多问题，如果我们想有效地解决比较字符串的问题，最朴素的办法是直接比较两个字符串，这样做的时间复杂度是O(min⁡(n1,n2))O(\min(n_1,n_2))，字符串哈希的想法在于，我们将每个字符串转换为一个整数，然后比较它们而不是字符串。

多项式哈希

哈希函数简单来说就是一个函数ff，它将输入映射到另外一个空间，以便于我们的操作。

哈希函数最重要的性质可以概括为下面两条：

  1. 如果两个对象相等，则它们的哈希值相等
  2. 如果两个哈希值相等，则对象很可能相等。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

当选择 Hash 函数时，你需要确保碰撞概率尽可能低

对于一个长度为ll的字符串ss来说，我们可以这样定义多项式 Hash 函数：

hash(s)=∑i=1ls[i]×pl−i( mod m)hash(s) = \sum_{i=1}^l s[i] \times p^{l-i}(\bmod m)

更进一步，考虑序列{a0,a1,…,an−1}\{a_0,a_1,\dots,a_{n-1}\}, 在这个序列从左到右的多项式散列下，我们可以得到多项式 Hash 函数：

hash(a,p,m)=(a0+a1⋅p+a2⋅p2+⋯+an−1⋅pn−1) mod mhash(a,p,m) = (a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots + a_{n-1} \cdot p^{n-1}) \bmod m

这里, bb和mm分别是基和哈希模块。

其中max⁡(ai)<p<m,gcd(p,m)=1\max(a_i) < p < m, gcd(p, m) = 1

O(1)比较时间

为了比较给定序列{a0,a1,…,an−1}\{a_0,a_1,\dots,a_{n-1}\}的片段，我们需要计算原始序列的每个前缀上的多项式散列。

将前缀上的多项式散列定义为：

pref(k,a,p,m)=(a0+a1⋅p+a2⋅p2+⋯+ak−1⋅pk−1) mod mpref(k,a,p,m) = (a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots + a_{k-1} \cdot p^{k-1}) \bmod m

我们将pref(k,a,p,m)pref(k,a,p,m)简要表示为pref(k)pref(k)。

一般形式：

pref(n)=(a0+a1⋅p+a2⋅p2+⋯+an−1⋅pn−1)pref(n) = (a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots + a_{n-1} \cdot p^{n-1})

每个前缀上的多项式散列可以在O(n)O(n)时间内计算，使用递推关系：

pref(k+1)=pref(k)+ak⋅pkpref(k+1) = pref(k) + a_k \cdot p^k

现在假设我们需要比较两个分别以aia_i和aja_j开头且长度为lenlen的子字符串

ai,ai+1,⋯ ,ai+len−1ANDaj,aj+1,⋯ ,aj+len−1a_i,a_{i+1},\cdots,a_{i+len-1} \quad AND \quad a_j,a_{j+1},\cdots,a_{j+len-1}

考虑pref(i+len)−pref(i)pref(i+len)-pref(i)和pref(j+len)−pref(j)pref(j+len)-pref(j)可以得到：

pref(i+len)−pref(i)=ai⋅pi+ai+1⋅pi+1+⋯+ai+len−1⋅pi+len−1pref(i+len) - pref(i) = a_i \cdot p^i + a_{i+1} \cdot p^{i+1} + \cdots + a_{i+len-1} \cdot p^{i+len-1}

pref(j+len)−pref(j)=aj⋅pj+aj+1⋅pj+1+⋯+aj+len−1⋅pj+len−1pref(j+len) - pref(j) = a_j \cdot p^j + a_{j+1} \cdot p^{j+1} + \cdots + a_{j+len-1} \cdot p^{j+len-1}

接着我们对两个式子进行简单转换，将第一个方程乘以pjp^j，将第二个方程乘以pip^i。我们得到:

pj⋅(pref(i+len)−pref(i))=pi+j⋅(ai+ai+1⋅p+⋯+ai+len−1⋅plen−1)p^j \cdot (pref(i+len) - pref(i)) = p^{i+j} \cdot(a_i + a_{i+1} \cdot p + \cdots + a_{i+len-1} \cdot p^{len-1})

pi⋅(pref(j+len)−pref(j))=pi+j⋅(aj+aj+1⋅p+⋯+aj+len−1⋅plen−1)p^i \cdot (pref(j+len) - pref(j)) = p^{i+j} \cdot(a_j + a_{j+1} \cdot p + \cdots + a_{j+len-1} \cdot p^{len-1})

可以发现，等式右侧括号中的多项式 Hash 正是我们期望的序列

因此，为了确定所需的序列段是否重合，我们需要检查以下等式

pj⋅(pref(i+len)−pref(i))=pi⋅(pref(j+len)−pref(j))p^j \cdot (pref(i+len) - pref(i)) = p^i \cdot (pref(j+len) - pref(j))

这样比较的时间复杂度是O(1)O(1)，最后加上mm可以得到:

pj⋅(pref(i+len)−pref(i)) mod m=pi⋅(pref(j+len)−pref(j)) mod mp^j \cdot (pref(i+len) - pref(i)) \bmod m = p^i \cdot (pref(j+len) - pref(j)) \bmod m

我们也可以在等式两边同时乘以p−i−jp^{-i-j}, 最终得到:

p−i⋅(pref(i+len)−pref(i)) mod m=p−j⋅(pref(j+len)−pref(j)) mod mp^{-i} \cdot (pref(i+len) - pref(i)) \bmod m = p^{-j} \cdot (pref(j+len) - pref(j)) \bmod m

对于另外一种哈希多项式，这里就不在赘述了，方法是相同的。

hash(a,p,m)=(a0⋅pn−1+a1⋅pn−2+⋯+an−2⋅p+an−1) mod mhash(a,p,m) = (a_0 \cdot p^{n-1} + a_1 \cdot p^{n-2} + \cdots + a_{n-2} \cdot p + a_{n-1} ) \bmod m

(pref(i+len)−pref(i)⋅plen) mod m=(pref(j+len)−pref(j)⋅plen) mod m(pref(i+len) - pref(i) \cdot p^{len}) \bmod m = (pref(j+len) - pref(j) \cdot p^{len}) \bmod m

计算子串的哈希值

在上面，我们定义了 Hash 函数，单次计算一个字符串的哈希值复杂度是O(n)O(n), 如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。

考虑序列{ai,ai+1,…,aj}\{a_i,a_{i+1},\dots,a_{j}\}

按照定义我们可以得到

hash(s[i⋯j])=ai+ai+1⋅p+⋯+aj⋅pj−ihash(s[i \cdots j]) = a_i + a_{i+1} \cdot p + \cdots + a_{j} \cdot p^{j-i}

考虑

hash(s[0⋯i−1])=a0+a1⋅p+⋯+ai−1⋅pi−1hash(s[0 \cdots i-1]) = a_0 + a_1 \cdot p + \cdots + a_{i-1} \cdot p^{i-1}

hash(s[0⋯j])=a0+a1⋅p+⋯+aj⋅pjhash(s[0 \cdots j]) = a_0 + a_1 \cdot p + \cdots + a_{j} \cdot p^{j}

根据前缀和思想，我们可以得到

hash(s[i⋯j])=p−i⋅(hash(s[0⋯j])−hash(s[0⋯i−1]))hash(s[i \cdots j]) = p^{-i} \cdot (hash(s[0 \cdots j]) - hash(s[0 \cdots i-1]))

对于多项式哈希的另外一种形式

hash(a,p,m)=(a0⋅pn−1+a1⋅pn−2+⋯+an−2⋅p+an−1) mod mhash(a,p,m) = (a_0 \cdot p^{n-1} + a_1 \cdot p^{n-2} + \cdots + a_{n-2} \cdot p + a_{n-1} ) \bmod m

按照同样的方法，我们也可以得到字串的哈希值:

hash(s[i⋯j])=hash(s[0⋯j])−hash(s[0⋯i−1])⋅pj−i+1hash(s[i \cdots j]) = hash(s[0 \cdots j]) - hash(s[0 \cdots i-1]) \cdot p^{j-i+1}

Hash 实现

1
2
3
4
5
6
7
8
9
10
11
M = int(1e9 + 7)
B = 233

def get_hash(s):
    res = 0
    for char in s:
        res = (res * B + ord(char)) % M
    return res

def cmp(s, t):
    return get_hash(s) == get_hash(t)

实际上，我们不可能在每次比较字符串时都计算一遍 Hash，这样的效率是低下的。

就像我们之前讨论的，O(1)O(1)时间复杂度进行查询

hash(s[i⋯j])=hash(s[0⋯j])−hash(s[0⋯i−1])⋅pj−i+1hash(s[i \cdots j]) = hash(s[0 \cdots j]) - hash(s[0 \cdots i-1]) \cdot p^{j-i+1} 

1
2
3
4
5
6
7
8
9
10
11
12
B = 233
M = 1e9 + 7
h, p = [0] * (n + 1), [0] * (n + 1)
p[0] = 1

def get_pref(s:str):
    for i in range(len(s)):
        h[i + 1] = (h[i] * B + ord(s[i])) % M
        p[i + 1] = (p[i] * B) % M

def find_sub(i:int, j:int) -> int:
    return (h[j] - h[i - 1] * p[j - i + 1]) % M;

最小化碰撞概率

对生日问题进行推广: 假设有 n 个人，每一个人都随机地从 N 个特定的数中选择出来一个数（N 可能是 365 或者其他的大于 0 的整数）。p(n)表示有两个人选择了同样的数字，这个概率有多大?

p≈1−exp⁡(−n22N)p \approx 1 - \exp(-\frac{n^2}{2N})

结论：在字符串哈希中，值域需要小到能够快速比较（10910^9、101810^{18}都是可以快速比较的）。同时，为了降低哈希冲突率，值域也不能太小。

Hash 应用

字符串匹配问题

核心思想：求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可。

最长回文子串

核心思想：二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。

最长公共子字符串

问题：给定mm个总长不超nn的非空字符串，查找所有字符串的最长公共子字符串，如果有多个，任意输出其中一个。

很显然如果存在长度为kk的最长公共子字符串，那么k−1k-1的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为kk，check(k)的逻辑为我们将所有所有字符串的长度为kk的子串分别进行哈希，将哈希值放入nn个哈希表中存储。之后求交集即可。

练习

参考资料