算法字符串

用字符串哈希解决经典问题：最长重复子串、最长公共子串

字数统计: 1.2k字   |   阅读时长: 5分
, , ,

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

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

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

一些字符串中的经典问题用字符串哈希都可以解决，比如最长重复子串（力扣 1044，187）、最长公共子串（力扣 718）。这些问题往往不止一种解决方案，本文我们用字符串哈希的方法解决这些问题，总览如下：

最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 “” 。

示例 1：
输入：s = “banana”
输出：”ana”

示例 2：
输入：s = “abcd”
输出：””

提示：

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

算法：值域二分+字符串哈希

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

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

代码 (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
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;
    }
};

最长公共子串

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1
2
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

算法：值域二分+字符串哈希

与最长重复子串类似。

代码 (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
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;
    }
};
Share