处理重复叠加串上的匹配问题:滚动哈希法

  |  

摘要: 滚动哈希例子

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


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

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

本文我们看一个适合用滚动哈希法处理的场景:重复叠加串上的匹配问题。

686. 重复叠加字符串匹配

给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。

注意:字符串 “abc” 重复叠加 0 次是 “”,重复叠加 1 次是 “abc”,重复叠加 2 次是 “abcabc”。

提示:

1
2
3
1 <= a.length <= 1e4
1 <= b.length <= 1e4
a 和 b 由小写英文字母组成

示例 1:
输入:a = “abcd”, b = “cdabcdab”
输出:3
解释:a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。

示例 2:
输入:a = “a”, b = “aa”
输出:2

示例 3:
输入:a = “a”, b = “a”
输出:1

示例 4:
输入:a = “abc”, b = “wxyz”
输出:-1

算法:字符串哈希

设 b 的长度为 m ,a 的长度为 n。记 $k = \left\lceil\frac{m}{n}\right\rceil$,则如果 a 的叠加串中有子串 b 的话,要么重复叠加了 k 次,要么叠加了 k + 1 次,取决于起点的位置。

首先求出 b 的哈希值 hash_b,然后求出 a 叠加 k 次后的叠加串中以 a[0] 为起点,长为 m 的子串的哈希值 hash_a

枚举起点 left = 1,2,...,n-1,过程中终点 right 也同步自增,如果出现自增后 right 等于 n,则叠加次数增加一次,将 k 更新为 k+1 即可。

枚举过程中,首先通过滚动哈希的方式更新 hash_a,然后对比 hash_ahash_b,若相等,在通过逐个字符对比的方式确认是否相等。

代码 (C++)

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
class Solution {
public:
int repeatedStringMatch(string a, string b) {
int n = a.size(), m = b.size();
ull hash_b = 0;
for(const char ch: b)
{
hash_b = hash_b * p;
hash_b = hash_b + ch;
}
ull hash_a = 0;
int right = 0;
int k = 1;
for(int i = 0; i < m; ++i)
{
hash_a = hash_a * p;
hash_a = hash_a + a[right];
right = (right + 1) % n;
if(i == m - 1 && hash_a == hash_b && check(a, 0, b))
return k;
if(right == 0)
k++;
}
ull power = quick_pow(p, m - 1);
for(int left = 1; left < n; ++left)
{
hash_a = hash_a - a[left - 1] * power;
hash_a = hash_a * p;
hash_a = hash_a + a[right];
right = (right + 1) % n;
if(hash_a == hash_b && check(a, left, b))
return k;
if(right == 0)
k++;
}
return -1;
}

private:
using ull = unsigned long long;
const ull p = 201326611;

bool check(const string& a, int i, const string& b)
{
int n = a.size(), m = b.size();
for(int j = 0; j < m; ++j)
{
if(a[i] != b[j])
return false;
i = (i + 1) % n;
}
return true;
}

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

Share