Hash 函数有助于解决很多问题,如果我们想有效地解决比较字符串的问题,最朴素的办法是直接比较两个字符串,这样做的时间复杂度是
,字符串哈希的想法在于,我们将每个字符串转换为一个整数,然后比较它们而不是字符串。
哈希函数简单来说就是一个函数fff,它将输入映射到另外一个空间,以便于我们的操作。
哈希函数最重要的性质可以概括为下面两条:
Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。
当选择 Hash 函数时,你需要确保碰撞概率尽可能低
对于一个长度为
的字符串
来说,我们可以这样定义多项式 Hash 函数:
更进一步,考虑序列
在这个序列从左到右的多项式散列下,我们可以得到多项式 Hash 函数:
这里, b和m分别是基和哈希模块。
其中
为了比较给定序列
的片段,我们需要计算原始序列的每个前缀上的多项式散列。
将前缀上的多项式散列定义为:
我们将
简要表示为
。
一般形式:
每个前缀上的多项式散列可以在
时间内计算,使用递推关系:
现在假设我们需要比较两个分别以
和
开头且长度为
的子字符串
考虑
可以得到:
接着我们对两个式子进行简单转换,将第一个方程乘以
,将第二个方程乘以
。我们得到:
可以发现,等式右侧括号中的多项式 Hash 正是我们期望的序列
因此,为了确定所需的序列段是否重合,我们需要检查以下等式
这样比较的时间复杂度是
,最后加上
可以得到:
我们也可以在等式两边同时乘以
, 最终得到:
对于另外一种哈希多项式,这里就不在赘述了,方法是相同的。
在上面,我们定义了 Hash 函数,单次计算一个字符串的哈希值复杂度是O(n)O(n)O(n), 如果需要多次询问一个字符串的子串的哈希值,每次重新计算效率非常低下。
考虑序列
按照定义我们可以得到
考虑
根据前缀和思想,我们可以得到
对于多项式哈希的另外一种形式
按照同样的方法,我们也可以得到字串的哈希值:
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都是可以快速比较的)。同时,为了降低哈希冲突率,值域也不能太小。
核心思想:求出模式串的哈希值后,求出文本串每个长度为模式串长度的子串的哈希值,分别与模式串的哈希值比较即可。
核心思想:二分答案,判断是否可行时枚举回文中心(对称轴),哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。
问题:给定mmm个总长不超nnn的非空字符串,查找所有字符串的最长公共子字符串,如果有多个,任意输出其中一个。
很显然如果存在长度为kkk的最长公共子字符串,那么k−1k-1k−1的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为kkk,check(k)
的逻辑为我们将所有所有字符串的长度为kkk的子串分别进行哈希,将哈希值放入nnn个哈希表中存储。之后求交集即可。