字符串哈希

  |  

摘要: 本文系统梳理了字符串哈希相关的要点,并通过字符串精确匹配问题给出代码模板。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们系统串讲一下字符串哈希算法。字符串哈希的哈希函数把任意长度的字符串 s (可以推广到数组 vec),映射成一个非负整数,并且冲突概率极低。

这种应用哈希算法来解决字符串匹配问题的算法,是 Rabin是 和是 Karp是 在是 1980是 年代初期,因此也称为 RK 算法。

首先介绍两个常用的哈希函数,然后研究如何对子串的哈希值进行高效处理,有前缀的方式和滚动的方式两种,其中前缀的方式有力扣 1392 和 1316 两道经典题,滚动方式处理的有力扣 686 经典题,最后要注意处理好溢出的情况。最后以字符串精确匹配为模板题,给出前缀处理和滚动处理两种计算子串哈希值的方法的代码模板。

本文内容总览如下:


要点1:哈希函数

字符串哈希函数有很多主流的设计方式,参考文章 字符串哈希的哈希函数,这里介绍最简单的两种,一般的问题够用。

哈希函数1:p 进制数

取一个固定值 p(一般取质数),对于字符串 s,长度为 m,则将 s 视为 m 位 p 进制数。给每个字符分配一个整数代表该字符,一般分配的字符都远小于 p。p 常用 131, 13331。

这样长为 m 的字符串 s 的哈希值就是该 m 位 p 进制数:

如果是很长的字符串 s 中的一个长为 m 的窗口 s[i..i+m-1],哈希函数 $hash(s[i..i+m-1])$ 如下:

生成一个长度为 m 的字符串的哈希码,需要 $O(m)$ 时间。

取一个固定值 MOD,求出的值对 MOD 取模,作为 s 最终的哈希值。

如果 MOD = $2^{64}$ ,可以直接用 unsigned long long 存储哈希值,自动对 $2^{64}$ 取模,这种方法叫自然溢出

哈希函数2:直接求和

直接将字符串中各个字母映射到 0~25 之后相加作为哈希值。相当于第一个哈希函数中 p 取 1 的情况。

长为 m 的字符串 s 的哈希函数:

很长的字符串 s 中的一个长为 m 的窗口的哈希函数:

生成一个长度为 m 的字符串的哈希码,依然需要 $O(m)$ 时间。

这种方法代码简单,不容易出错,但是比第一个函数容易冲突。

要点2:子串的哈希值

用字符串哈希算法做字符串精确匹配还有一个关键问题要解决:摊销 $O(1)$ 地生成各个窗口的哈希码,有两种办法,一种是滚动的方式处理,一种是前缀的方式处理。

前缀方式处理

将 s 中的每个前缀对应的哈希值先预处理出来,记录在 prefix_hash 中。

  • 当 i = 0 时,prefix_hash[i] = 0,表示空前缀的哈希值,
  • 当 i > 0 时,prefix_hash[i] := 前缀 s[0..i-1] 的哈希值

prefix_hash 的过程与推前缀和的过程很像,如下:

1
2
3
4
5
6
7
8
vector<unsigned long long> prefix_hash(n + 1, 0);
vector<unsigned long long> pp(n + 1, 0);
pp[0] = 1;
for(int i = 1; i <= n; ++i)
{
prefix_hash[i] = prefix_hash[i - 1] * p + s[i - 1];
pp[i] = pp[i - 1] * p;
}

代码中 pp 用于维护 p 的幂:pp[i]:= p 的 i 次幂,其中 pp[0] = 1

利用 prefix_hash 可以 O(1) 地求出 s 上任意子串的哈希值,这一点类似前缀和。例如当前窗口 [l, r] 上的哈希值如下, 其中窗口长度为 len

1
unsigned long long hash = (prefix_hash[r] - prefix_hash[l - 1] * pp[len]);

例题:

滚动方式处理

利用滑动窗口的特性,每次滑动都有一个元素进,一个元素出。因此当窗口前进一位的时候。

考虑当前窗口,窗长为 len,起点为 i,上一个窗口的起点为 i - 1,上一个窗口的哈希值为 hash_substr,新的窗口中删除了元素 s[i-1],增加了 s[i+len-1],因此只需要在上一个窗口的哈希值 hash_substr 的基础上,处理删除和增加的两个字符对哈希值的贡献即可

以哈希函数2 为例:

1
2
3
hash_substr = hash_substr - s[i - len] * pp[len];
hash_substr = hash_substr * p;
hash_substr = hash_substr + s[i];

例题:

要点3:避免溢出

pp[i] 可能是很大的数字,需要通过取模 MOD 的方式设置一个上限,用 hash % MOD 代替原来的哈希值 hash

具体有两种方式:

  • 一种是将 hash 值的类型设为 unsigned long long,若出现溢出,相当于自动模了 $2^{64}$。
  • 另一种是设一个 MOD 的值,在计算哈希值的各个中间环节中都取模,避免溢出。

总结

字符串哈希算法关键的三点,哈希函数,子串的哈希值,避免溢出


模板题:字符串精确匹配

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

提示:

1
2
1 <= haystack.length, needle.length <= 1e4
haystack 和 needle 仅由小写英文字符组成

示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:”leeto” 没有在 “leetcode” 中出现,所以返回 -1 。

算法:字符串哈希

用字符串哈希做精确匹配也称 Rabin Karp 算法。

对 pattern 生成一个哈希值。对 s 中的每个长度为 m 的窗口(即 BF 算法中枚举的子串)生成一个哈希值。

对两个哈希值作比较,如果哈希值不相等,则当前窗口与 p 一定不匹配,如果哈希值相等,则当前窗口与 p 可能匹配,也可能不匹配(发生哈希冲突的情况),需要对当前窗口和 p 进行一次逐一比较进行确认。逐一比较确认的目的是排除两个长为 m 的不同字符串哈希值相同,即哈希冲突的情况。

BF 算法(参考文章 字符串精确匹配)中每个窗口都要做逐一比较,而字符串哈希的方法只有哈希值相等的时候才会做逐一比较。

代码1 (C++,模板,前缀法)

  • 模板:哈希函数1 + 前缀哈希 + 预处理 $p^{i}$

p, mod 的质数选取: 201326611, 402653189, 1610612741。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
int strStr(string s, string pattern) {
if(pattern.empty())
return 0;
if(s.empty())
return -1;
int n = s.size(), m = pattern.size();
if(n < m)
return -1;

// n > 0, m > 0, n >= m
const int MOD = 1610612741;
const int p = 201326611;
using ll = long long;

// 主串的前缀哈希数组
vector<ll> prefix_hash(n + 1, 0);
vector<ll> pp(n + 1, 0); // 使用 MOD 的时候不能用 unsigned long long
pp[0] = 1;
for(int i = 1; i <= n; ++i)
{
prefix_hash[i] = (prefix_hash[i - 1] * p + (s[i - 1] - 'a')) % MOD;
pp[i] = (pp[i - 1] * p) % MOD;
}

// 模式串的哈希值
ll pattern_hash = 0;
for(int i = 0; i < m; ++i)
pattern_hash = (pattern_hash * p + (pattern[i] - 'a')) % MOD;

// 长度为 m 的子串, hash数组中对应位置 [l, r] -- [1..n-m+1, m..n]
// p 的幂,只需要 m - 1 次
for(int i = 1; i <= n - m + 1; ++i)
{
int l = i, r = i + m - 1;
ll hash = ((prefix_hash[r] - prefix_hash[l - 1] * pp[m]) % MOD + MOD) % MOD;
if(hash == pattern_hash)
{
int start = i - 1;
int j = 0;
while(j < m && s[start + j] == pattern[j])
j++;
if(j == m)
return start;
}
}
return -1;
}
};

代码2 (C++,模板,滚动法)

  • 哈希函数1 + 滚动哈希 + 预处理 $p^{i}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
int strStr(string s, string pattern) {
if(pattern.empty())
return 0;
if(s.empty())
return -1;
int n = s.size(), m = pattern.size();
if(n < m)
return -1;

// n > 0, m > 0, n >= m
const int MOD = 1610612741;
const int p = 201326611;
using ll = long long;

// 模式串的哈希值
ll pattern_hash = 0;
for(int i = 0; i < m; ++i)
pattern_hash = (pattern_hash * p + (pattern[i] - 'a')) % MOD;

// p 的幂,只需要 m - 1 次
vector<ll> pp(m, 0); // 使用 MOD 的时候不能用 unsigned long long
pp[0] = 1;
ll hash_substr = 0;
for(int i = 0; i < m; ++i)
{
hash_substr = (hash_substr * p + (s[i] - 'a')) % MOD;
if(i > 0)
pp[i] = (pp[i - 1] * p) % MOD;
}
if(hash_substr == pattern_hash)
{
int i = 0;
while(i < m && s[i] == pattern[i])
i++;
if(i == m)
return 0;
}
// 开始滚动
for(int i = m; i < n; ++i)
{
int start = i - m + 1;
hash_substr = ((hash_substr - (s[start - 1] - 'a') * pp[m - 1]) % MOD + MOD) % MOD;
hash_substr = (hash_substr * p) % MOD;
hash_substr = (hash_substr + (s[i] - 'a')) % MOD;
if(hash_substr == pattern_hash)
{
int j = 0;
while(j < m && s[start + j] == pattern[j])
j++;
if(j == m)
return start;
}
}
return -1;
}
};

Share