字符串之字符串哈希

字符串之字符串哈希

前言

Hash 函数有助于解决很多问题，如果我们想有效地解决比较字符串的问题，最朴素的办法是直接比较两个字符串，这样做的时间复杂度是

，字符串哈希的想法在于，我们将每个字符串转换为一个整数，然后比较它们而不是字符串。

多项式哈希

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

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

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

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

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

对于一个长度为

的字符串

来说，我们可以这样定义多项式 Hash 函数：

更进一步，考虑序列

在这个序列从左到右的多项式散列下，我们可以得到多项式 Hash 函数：

这里, b和m分别是基和哈希模块。

其中

O(1)比较时间

为了比较给定序列

的片段，我们需要计算原始序列的每个前缀上的多项式散列。

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

我们将

简要表示为

。

一般形式：

每个前缀上的多项式散列可以在

时间内计算，使用递推关系：

现在假设我们需要比较两个分别以

和

开头且长度为

的子字符串

考虑

可以得到：

接着我们对两个式子进行简单转换，将第一个方程乘以

，将第二个方程乘以

。我们得到:

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

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

这样比较的时间复杂度是

，最后加上

可以得到:

我们也可以在等式两边同时乘以

, 最终得到:

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

计算子串的哈希值

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

考虑序列

按照定义我们可以得到

考虑

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

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

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

Hash 实现

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，这样的效率是低下的。

就像我们之前讨论的，

时间复杂度进行查询

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)表示有两个人选择了同样的数字，这个概率有多大?

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

Hash 应用

字符串匹配问题

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

最长回文子串

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

最长公共子字符串

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

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

练习

• A Needle in the Haystack - SPOJ
• Double Profiles - Codeforces
• Password - Codeforces
• SUB_PROB - SPOJ
• INSQ15_A
• SPOJ - Ada and Spring Cleaning
• GYM - Text Editor
• 12012 - Detection of Extraterrestrial
• Codeforces - Games on a CD
• UVA 11855 - Buzzwords
• Codeforces - Santa Claus and a Palindrome
• Codeforces - String Compression
• Codeforces - Palindromic Characteristics
• SPOJ - Test
• Codeforces - Palindrome Degree
• Codeforces - Deletion of Repeats

参考资料

• 字符串哈希
• Rolling hash and 8 interesting problems
• String Hashing