算法字符串

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

字数统计: 1.8k字   |   阅读时长: 9分
, , ,

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

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

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

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

最长重复子串

给你一个字符串 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;
    }
};

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

提示：

1
2
1 <= s.length <= 1000
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // prefix_hash[i] 为 s[0..i-1] 的哈希值
        prefix_hash = vector<ull>(n + 1, 0);
        // prefix_hash[i] 为 s[i..n-1] 的哈希值
        suffix_hash = vector<ull>(n + 1, 0);
        pp = vector<ull>(n + 1, 1);
        for(int i = 1; i <= n; ++i)
        {
            prefix_hash[i] = prefix_hash[i - 1] * p + (ull)s[i - 1];
            suffix_hash[n - i] = suffix_hash[n - i + 1] * p + (ull)s[n - i];
            pp[i] = pp[i - 1] * p;
        }

        // 奇数长度的回文串
        int left = 1, right = (n + 1) / 2;
        int start_odd = 0;
        while(left < right)
        {
            int mid = (left + right + 1) / 2;
            int k = check_odd(s, mid);
            if(k != -1)
            {
                start_odd = k;
                left = mid;
            }
            else
                right = mid - 1;
        }
        int len_odd = left * 2 - 1;

        // 偶数长度的回文串
        left = 0, right = (n + 1) / 2;
        int start_even = 0;
        while(left < right)
        {
            int mid = (left + right + 1) / 2;
            int k = check_even(s, mid);
            if(k != -1)
            {
                start_even = k;
                left = mid;
            }
            else
                right = mid - 1;
        }
        int len_even = left * 2;
        if(len_even > len_odd)
            return s.substr(start_even, len_even);
        else
            return s.substr(start_odd, len_odd);
    }

private:
    using ull = unsigned long long;
    const ull p = 201326611;
    vector<ull> prefix_hash, suffix_hash, pp;

    int check_odd(const string& s, int mid)
    {
        // 有没有半径为 mid 的奇数长回文子串
        int n = s.size();
        int r = mid;
        for(int k = r - 1; k <= n - r; ++k)
        {
            // s[k-r+1..k] 与 s[k..k+r-1]
            ull hash_left = prefix_hash[k + 1] - prefix_hash[k - r + 1] * pp[r];
            ull hash_right = suffix_hash[k] - suffix_hash[k + r] * pp[r];
            if(hash_left == hash_right)
                if(check_conflict(s, k, k, r))
                    return k - r + 1;
        }
        return -1;
    }

    int check_even(const string& s, int mid)
    {
        // 有没有半径为 mid 的偶数长回文子串
        int n = s.size();
        int r = mid;
        for(int k = r - 1; k <= n - r - 1; ++k)
        {
            // s[k-r+1..k] 与 s[k+1..k+r]
            ull hash_left = prefix_hash[k + 1] - prefix_hash[k - r + 1] * pp[r];
            ull hash_right = suffix_hash[k + 1] - suffix_hash[k + r + 1] * pp[r];
            if(hash_left == hash_right)
                if(check_conflict(s, k, k + 1, r))
                    return k - r + 1;
        }
        return -1;
    }

    bool check_conflict(const string& s, int l, int r, int len)
    {
        // s[l-len+1..l] 与 s[r..r+len-1] 是否对称
        for(int i = 0; i < len; ++i)
        {
            if(s[l - i] != s[r + i])
                return false;
        }
        return true;
    }
};
Share