力扣1044-Longest Duplicate Substring C++

2021-10-01

Word count: 1.4k | Reading time≈ 6 min

1635668255065

原题链接点击这里，说句题外话，通过这题发现美国站力扣社区的解题思路还是比较丰富一点。力扣的官方题解有些地方表达的不是很清楚。下面给出二分查找+Rabin Karp解法的分析，后缀数组解法见这里

题目的意思是给出一个字符串s，找到其中最少出现两次的重复子串（重复子串可以重叠）。返回具有这样重复子串性质的最长子串。如果没有找到返回空。首先这个题目就比较绕。来看一下Example 1：

字符串中"banana"中子串"ana"出现了2次（尽管两次出现的"ana"有交叠），且长度为3，该字符串中不存在长度大于3的重复子串，因此"ana"就是我们要求的目标。对于单个字符’a’尽管出现了3次，但它本身的长度为1，小于"ana"的长度，所以没有考虑。下面开始分析此题

假设字符串的长度为L，选出的重复子串长度为k，那么显然k要从L-1搜索到1。对于每个长度k，每次从原始串中进行选取，然后比较判断是否已经存在。可以看到这里涉及到一个map/set的结构判断重复。下面给出k=3时的判断过程：

1635669577152

如图所示，当k=3时需要判断途中四个备用子串是否存在重复，很明显"ana"身在其中。而当k=4时，备用子串"bana"、“anan”、"nana"不存在重复。因此"ana"就是本例的解。那么该如何寻找长度k呢。很显然可以用循环的方式遍历，但这样效率很低。由于我们要查找的长度是有序的[1, L-1]。因此可以采用二分查找的方式搜索最优解，

另外一个要关注的问题就是如何快速的判断子串是否出现重复。对于这个子问题，暴力的做法是把这些子串都从原始串中取出来，进行记录判重。这样做使得算法复杂度变为O( $L^2*logL$ )显然会超时，因此就有了下面要提到的Robin-Karp算法、其实就是将字符串编码成一个26进制（字符串s仅包含小写字母）的大整数作为key，来进行判断。

以start = 0，“ban”，k=3为例，它对应的整数分别为1, 0, 13映射成的 $f("ban")$ 为

f("ban") = 1 * 26^2 + 0 * 26^1 + 13 * 26^0

将其扩展到一般情况就是

f("substr") = s'[0] * h^{k-1} + s'[1]*h^{k-2} + \cdots + s'[k-1] * h^0

其中h表示h进制数，此题为26。 $s'[i]$ 表示将单个字符映射成的整数值(从0开始)。当start往后移动时，只需要减去最高位的26进制，整体左移一位，同时加上最低位的26进制即可。还是以Example为例，“ban"往后移动一位为"ana”，计算 $f("ana")$ ：

f("ana") = (f("ban") - 1 * 26^2) * 26 + 1 * 26^0 \\ = (26 * f("ban") - 1 * 26^3) + 1*26^0

于是就有了下面的通式

f("next substr") = f("substr")*h - h^k + s'[i]

注意 $h^k$ 可能很大，为了保证结果的一致性，一般取其怕平方作为上界进行取余。取余之后就可能存在编码一样，但字串其实不一样的结果，因此在题解中存的是字符串起始位置列表进行判断。这样就万无一失啦！

C++代码如下

class Solution {
public:
    string longestDupSubstring(string s) {
        // 二分查找+Rabin-Karp
        int left = 1;
        int a = 26;
        int right = s.length();
        vector<int> record;
        for(auto ch:s) record.push_back(ch - 'a');
        // 重复子串长度搜索[1, len)
        while(left < right){
            int mid = left + (right - left) / 2;
            if(search(s, a, mid, record) != -1){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        int start = search(s, a, left-1, record); // 找到长度为left的重复字符的起始位置
        return start != -1 ? s.substr(start, left-1) :"";
    }
    int search(string s, int a, int len, vector<int> &record){
        if(len == 0) return -1;
        long al = 1; // a的l次方
        long code = 0;
        long long modules = pow(2.0,32) - 1;
        int sslen = s.length();
        unordered_map<long long, vector<long long>> hash;
        for(int i = 0;i < len;i++){
            code = (code * a + record[i]) % modules;
            al = (al * a) % modules;
        }
        hash[code] = {0};
        for(int i = 1;i < sslen - len + 1; i++){
            code = (code * a - al * record[i-1] % modules  + modules) % modules;
            code = (code + record[i+len-1]) % modules;
            if(hash.find(code) == hash.end())   hash[code] = {i};
            else{
                for(int index: hash[code]) {
                    if(s.substr(index, len) == s.substr(i, len)) return i;
                }
                hash[code].push_back({i});
            }
        }
        
        return -1;
    }
};

对该解答有问题欢迎留言。

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.