力扣1044.Longest Duplicate Substring C++ Accepted

本文主要是介绍力扣1044.Longest Duplicate Substring C++ Accepted，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接点击这里，说句题外话，通过这题发现美国站力扣社区的解题思路还是比较丰富一点。力扣的官方题解有些地方表达的不是很清楚。下面给出二分查找+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时的判断过程：

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

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

以start = 0，“ban”，k=3为例，它对应的整数分别为1, 0, 13映射成的 f ( " b a n " ) f("ban") f("ban")为
f ( " b a n " ) = 1 ∗ 2 6 2 + 0 ∗ 2 6 1 + 13 ∗ 2 6 0 f("ban") = 1 * 26^2 + 0 * 26^1 + 13 * 26^0 f("ban")=1∗262+0∗261+13∗260
将其扩展到一般情况就是
f ( " s u b s t r " ) = s ′ [ 0 ] ∗ h k − 1 + s ′ [ 1 ] ∗ h k − 2 + ⋯ + s ′ [ k − 1 ] ∗ h 0 f("substr") = s'[0] * h^{k-1} + s'[1]*h^{k-2} + \cdots + s'[k-1] * h^0 f("substr")=s′[0]∗hk−1+s′[1]∗hk−2+⋯+s′[k−1]∗h0
其中h表示h进制数，此题为26。 s ′ [ i ] s'[i] s′[i]表示将单个字符映射成的整数值(从0开始)。当start往后移动时，只需要减去最高位的26进制，整体左移一位，同时加上最低位的26进制即可。还是以Example为例，“ban"往后移动一位为"ana”，计算 f ( " a n a " ) f("ana") f("ana")：
f ( " a n a " ) = ( f ( " b a n " ) − 1 ∗ 2 6 2 ) ∗ 26 + 1 ∗ 2 6 0 = ( 26 ∗ f ( " b a n " ) − 1 ∗ 2 6 3 ) + 1 ∗ 2 6 0 f("ana") = (f("ban") - 1 * 26^2) * 26 + 1 * 26^0 \\ = (26 * f("ban") - 1 * 26^3) + 1*26^0 f("ana")=(f("ban")−1∗262)∗26+1∗260=(26∗f("ban")−1∗263)+1∗260
于是就有了下面的通式
f ( " n e x t s u b s t r " ) = f ( " s u b s t r " ) ∗ h − h k + s ′ [ i ] f("next substr") = f("substr")*h - h^k + s'[i] f("nextsubstr")=f("substr")∗h−hk+s′[i]
注意 h k h^k hk可能很大，为了保证结果的一致性，一般取其怕平方作为上界进行取余。取余之后就可能存在编码一样，但字串其实不一样的结果，因此在题解中存的是字符串起始位置列表进行判断。这样就万无一失啦！

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;
    }
};

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

这篇关于力扣1044.Longest Duplicate Substring C++ Accepted的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！