算法字符串

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

字数统计: 869字   |   阅读时长: 3分
, ,

摘要: 滚动哈希例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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_a 与 hash_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