[LeetCode] 1044. Longest Duplicate Substring

[grandyang]

Given a string s, consider all  duplicated substrings : (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Example 1:

Input: s = "banana"
Output: "ana"

Example 2:

Input: s = "abcd"
Output: ""

Constraints:

• 2 <= s.length <= 3 * 104
• s consists of lowercase English letters.

这道题给了一个字符串s，让找出最长的重复子串，且说明了重复子串可以重叠，若不存在，则返回空串。虽然博主之前说过玩字符串求极值的题十有八九都是用动态规划来做，but，这道题是个例外，因为很难实现子问题的重现，从而很难写出状态转移方程。实际上这道题是应该用二分搜索法来做的，因为最长重复子串的长度是有范围的，是0到n之间，对于二分到的长度 mid，使用 Rabin–Karp 算法来快速找到原字符串中是否存在长度为 mid 的重复子串。然后跟结果 res 比较，若大于 res，则更新 res 且 left 赋值为 mid+1，否则 right 赋值为 mid。接下来说说这个 Rabin–Karp 算法，是一种快速的字符串比较算法，跟 KMP 算法一样都是字符串匹配的算法，关于 KMP 算法可以参见博主之前的帖子 KMP Algorithm 字符串匹配算法KMP小结。这里的 Rabin–Karp 算法跟 KMP 有很大的不同，主要是将相同都子串都编码成一个 Hash 值，这样只要查找该 Hash 值是否存在就可以快速知道该子串是否存在。编码的方法是用 26 进制，因为限制了都是小写字母，为了防止整型溢出，需要对一个超大的质数取余。这里找重复子串利用到了一个滑动窗口，首先对窗口中的字符串编码成 26 进制，并且用一个 HashMap 将这个编码值映射到该子串的起始坐标的集合。然后就要移动滑动窗口了，首先需要去掉最左边的一个字符，那么编码值会如何变化呢，来看一个简单的例子 "bcd"，编码值的计算式为 ((1 * 26) + 2) * 26 + 3，化简一下为 1 * 26^2 + 2 * 26 + 3，实际上要减去的值为 1 * 26^2。由于滑动窗口的长度可能很大，为了不每次都从头开始计算 26 的次方，使用一个 power 数组来缓存 26 的次方，由于还是可能整型溢出，所以还是要对一个超大质数取余，这里的超大质数使用 1e7，也可以使用别的，但是注意起码要小于 INT_MAX/26，不然还是会有溢出的风险。加上的新的字符就比较简单了，当前的编码值乘以 26 再加上新的字符值。接下来看这个新得到的编码值，假如在 HashMap 中不存在，则映射到新的数组；若存在，则遍历当前映射值的数组，分别取出对应的子数组，若和当前子串相同，则返回，否则将当前子串起始位置加入到映射数组中，参见代码如下：

class Solution {
public:
    string longestDupSubstring(string s) {
        string res;
        int n = s.size(), left = 0, right = n, M = 1e7 + 7;
        vector<int> power(n);
        for (int i = 0; i < n; ++i) {
            power[i] = (i == 0) ? 1 : (power[i - 1] * 26) % M;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            string dup = rabinKarp(s, mid, power);
            if (dup.size() > res.size()) {
                res = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return res;
    }
    string rabinKarp(string s, int len, vector<int>& power) {
        if (len == 0) return "";
        int n = s.size(), cur = 0, M = 1e7 + 7;
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < len; ++i) {
            cur = (cur * 26 + (s[i] - 'a')) % M;
        }
        hash[cur] = {0};
        for (int i = len; i < n; ++i) {
            cur = ((cur - power[len - 1] * (s[i - len] - 'a')) % M + M) % M;
            cur = (cur * 26 + (s[i] - 'a')) % M;
            if (!hash.count(cur)) {
                hash[cur] = {i - len + 1};
            } else {
                for (int idx : hash[cur]) {
                    if (s.substr(idx, len) == s.substr(i - len + 1, len)) return s.substr(idx, len);
                }
                hash[cur].push_back(i - len + 1);
            }
        }
        return "";
    }
};

Github 同步地址:

#1044

参考资料：

https://leetcode.com/problems/longest-duplicate-substring/

https://leetcode.com/problems/longest-duplicate-substring/discuss/694963/Beats-100-using-Trie-tree

https://leetcode.com/problems/longest-duplicate-substring/discuss/695197/C%2B%2B-Binary-Seach-with-Robin-Karp-Algorithm-O(nlogn)

LeetCode All in One 题目讲解汇总(持续更新中...)