字符串哈希

  |  

摘要: 本文系统梳理了字符串哈希相关的要点。并汇总了 leetcode 上的相关的题目。

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



$0 字符串哈希

字符串哈希是一种哈希函数,把任意长度的字符串 s (可以推广到数组 vec),映射成一个非负整数,并且冲突概率极低。

(1) 哈希函数

字符串哈希函数有很多主流的设计方式

哈希函数1

取一个固定值 p,将 s 视为 p 进制数,给每个字符分配一个整数代表该字符,一般分配的字符都远小于 p。

p 常用 131, 13331

对于 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 的字符串的哈希码,依然需要 $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 的过程与推前缀和的过程很像,如下:

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

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;
}

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

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

1392. 最长快乐前缀

1316. 不同的循环子字符串

滚动方式处理

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

考虑当前窗口,窗长为 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];

686. 重复叠加字符串匹配

(3) 避免溢出

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

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


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


$1 经典问题的字符串哈希解法

(1) 字符串精确匹配

28. 实现 strStr()

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

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

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

BF 算法中每个窗口都要做逐一比较,而字符串哈希的方法只有哈希值相等的时候才会做逐一比较。

代码

(模板:哈希函数1 + 前缀哈希 + 取模MOD + 预处理 $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
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;
// 主串的前缀哈希数组
vector<long long> prefix_hash(n + 1, 0);
vector<long long> 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;
}
// 模式串的哈希值
long long 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;
long long hash = ((prefix_hash[r] - prefix_hash[l - 1] * pp[m]) % MOD + MOD) % MOD;
if(hash == pattern_hash)
return i - 1;
}
return -1;
}
};

(2) 最长重复子串

1044. 最长重复子串 / 187. 重复的DNA序列

二分长度,检查 s 中有无长度为 mid 的重复子串

  • 若有,则 left = mid
  • 若没有,则 right = mid - 1

代码

(模板: 哈希函数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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public:
string longestDupSubstring(string S) {
int n = S.size();
int left = 0, right = n - 1;
while(left < right)
{
int mid = (left + right + 1) / 2;
int idx = check(S, mid);
if(idx != -1)
left = mid;
else
right = mid - 1;
}
if(left == 0) return "";
int idx = check(S, left);
return S.substr(idx, left);
}

private:
using ull = unsigned long long;
const ull p = 201326611;
unordered_map<ull, vector<int>> mapping; // hash -> idx

int check(const string& S, int l)
{
int n = S.size();
ull power = quick_pow(p, l - 1);
ull hash = 0;
for(int i = 0; i < l; ++i)
{
hash = hash * p;
hash = hash + (ull)(S[i] - 'a');
}
mapping.clear();
mapping[hash].push_back(0);
for(int i = l; i < n; ++i)
{
hash = hash - (ull)(S[i - l] - 'a') * power;
hash = hash * p;
hash = hash + (ull)(S[i] - 'a');
if(mapping.count(hash) > 0)
{
for(int j: mapping[hash])
if(check_conflict(S, l, j, i - l + 1))
return i - l + 1;
}
mapping[hash].push_back(i - l + 1);
}
return -1;
}

bool check_conflict(const string& S, int l, int i, int j)
{
for(int k = 0; k < l; ++k)
if(S[i + k] != S[j + k])
return false;
return true;
}

ull quick_pow(ull a, ull n)
{
ull ans = 1;
while(n)
{
if(n & 1)
ans = ans * a;
a = a * a;
n >>= 1;
}
return ans;
}
};

(3) 最长公共子串

718. 最长重复子数组

与最长重复子串类似,二分 + 字符串哈希

代码

(模板: 哈希函数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
59
60
61
62
63
64
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int na = A.size(), nb = B.size();
if(na < nb) return findLength(B, A);
// na >= nb
vector<ull> hashA(na + 1, 0);
for(int i = 1; i <= na; ++i)
hashA[i] = hashA[i - 1] * p + (ull)A[i - 1];
vector<ull> hashB(nb + 1, 0);
vector<ull> pp(nb + 1, 1);
for(int i = 1; i <= nb; ++i)
{
hashB[i] = hashB[i - 1] * p + (ull)B[i - 1];
pp[i] = pp[i - 1] * p;
}

int left = 0, right = nb;
while(left < right)
{
int mid = (left + right + 1) / 2;
mapping.clear();
for(int i = 0; i <= na - mid; ++i)
{
ull hasha = hashA[i + mid] - hashA[i] * pp[mid];
mapping[hasha].insert(i);
}

bool matched = false;
for(int j = 0; j <= nb - mid; ++j)
{
ull hashb = hashB[j + mid] - hashB[j] * pp[mid];
if(mapping.count(hashb) == 0)
continue;
for(int i: mapping[hashb])
if(check_conflict(A, i, B, j, mid))
{
matched = true;
break;
}
}
if(matched)
left = mid;
else
right = mid - 1;
}
return left;
}

private:
using ull = unsigned long long;
const ull p = 201326611;
unordered_map<ull, unordered_set<int>> mapping;

bool check_conflict(vector<int>& A, int i, vector<int>& B, int j, int mid)
{
for(int k = 0; k < mid; ++k)
{
if(A[i + k] != B[j + k])
return false;
}
return true;
}
};

(4) 字符串同构

205. 同构字符串

  • 判断 s 和 t 是否同构。

890. 查找和替换模式

  • 从 words 中找到所有与 p 同构的单词

对 s 求哈希函数时,先将其中每个字符根据某种规则映射到另一字符,再代入哈希函数的公式

代码中的 get_mapping 就是在确定一个这样的映射规则。

代码

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
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
string new_p = get_mapping(pattern);
vector<string> result;
for(const string& s: words)
{
string new_s = get_mapping(s);
if(new_s == new_p)
result.push_back(s);
}
return result;
}

private:
unordered_map<char, char> mapping;

string get_mapping(const string& s)
{
mapping.clear();
char iter = 'a';
for(const char& ch: s)
{
if(mapping.count(ch) > 0)
continue;
mapping[ch] = iter++;
}
string result = s;
for(char &ch: result)
ch = mapping[ch];
return result;
}
};

Share