力扣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\ast logL$)显然会超时，因此就有了下面要提到的Robin-Karp算法、其实就是将字符串编码成一个26进制（字符串s仅包含小写字母）的大整数作为key，来进行判断。

以start = 0，“ban”，k=3为例，它对应的整数分别为1, 0, 13映射成的$f("ban")$为
$$f("ban")=1\ast 26^2+0\ast 26^1+13\ast 26^0$$
将其扩展到一般情况就是
$$f("substr")=s^{\prime }[0]\ast h^{k-1}+s^{\prime }[1]\ast h^{k-2}+\cdots +s^{\prime }[k-1]\ast h^0$$
其中h表示h进制数，此题为26。$s^{\prime }[i]$表示将单个字符映射成的整数值(从0开始)。当start往后移动时，只需要减去最高位的26进制，整体左移一位，同时加上最低位的26进制即可。还是以Example为例，“ban"往后移动一位为"ana”，计算$f("ana")$：
$$\begin{gathered} f("ana")=(f("ban")-1\ast 26^2)\ast 26+1\ast 26^0 \\ =(26\ast f("ban")-1\ast 26^3)+1\ast 26^0 \end{gathered}$$
于是就有了下面的通式
$$f("nextsubstr")=f("substr")\ast h-h^k+s^{\prime }[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;
    }
};
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

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