多次查询两个子串是否相等:前缀哈希法

  |  

摘要: 可以用字符串哈希解决的经典问题

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


在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。

一些字符串中的经典问题用字符串哈希都可以解决,比如最长重复子串(力扣 1044,187)、最长公共子串(力扣 718)、最长回文子串(力扣 5)。这些问题往往不止一种解决方案,在文章 用字符串哈希解决经典问题:最长重复子串、最长公共子串、最长回文子串 中我们用字符串哈希的方法解决了这些问题,

本文我们看一个适合用前缀哈希法处理的场景:在一个串上反复查询子串的哈希值。

两个子串是否相等,多次查询

给定一个很长的 DNA 序列(该 DNA 序列可能包含 26 个小写英文字母)。

然后我们每次选择两个区间,询问两个子串对应的 DNA 序列是否相等。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第一行输入一个 DNA 字符串 S。
第二行一个数字 m,表示 m 次询问。
接下来 m 行,每行四个数字 l1,r1,l2,r ,分别表示此次询问的两个区间,注意字符串的位置从 1 开始编号。

输出格式
对于每次询问,输出一行表示结果。
如果两只兔子完全相同输出 Yes,否则输出 No(注意大小写)。

数据范围
1 <= length(S),m <= 1000000

输入样例:
aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2

输出样例:
Yes
No
Yes

算法:字符串哈希

预处理 s 的前缀哈希 prefix_hash。记 pp[i] 为 $p$ 的 $i$ 次幂。

给定区间 s[l..r],其哈希值为 prefix_hash[r+1] - prefix_hash[l] * pp[r - l + 1]

如果两个哈希值相等,就认为两个子串是相等的,这样会有小概率发生哈希冲突,即哈希值相同的两个子串实际不相等,导致错判。

如果要完全避免哈希冲突造成的错判,可以进行逐一字符比较,确认两个子串是否真相等。但最坏情况的时间复杂度就很高了。

代码 (C++)

如果执行 check 判断哈希值相同的两个子串是否真相等,则时间上无法通过,将 check 去掉,可以赌小概率的哈希冲突不会发生。

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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool check(const string& s, int l1, int r1, int l2, int r2)
{
for(int k = 0; k < r1 - l1 + 1; ++k)
if(s[l1 + k] != s[l2 + k])
return false;
return true;
}

int main()
{
string s;
cin >> s;

using ull = unsigned long long;
const ull p = 1610612741;

int n = s.size();
vector<ull> prefix_hash(n + 1), pp(n + 1, 1);
for(int i = 1; i <= n; ++i)
{
prefix_hash[i] = prefix_hash[i - 1] * p + (ull)s[i - 1];
pp[i] = pp[i - 1] * p;
}

int m;
cin >> m;
for(int i = 0; i < m; ++i)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
ull hash1 = prefix_hash[r1] - prefix_hash[l1 - 1] * pp[r1 - l1 + 1];
ull hash2 = prefix_hash[r2] - prefix_hash[l2 - 1] * pp[r2 - l2 + 1];
if(hash1 != hash2)
cout << "No" << endl;
else
{
if(check(s, l1, r1, l2, r2))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}

Share