最长重复子串

1044. 最长重复子串

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

示例 1：
输入："banana"
输出："ana"
示例 2：
输入："abcd"
输出：""
提示：

2 <= S.length <= 10^5
S 由小写英文字母组成。

方法一：二分查找 + Rabin-Karp 字符串编码
分析

我们可以把这个问题分解成两个子问题：

从 1 到 N 中选取子串的长度 L；

检查字符串中是否存在长度为 L 的重复子串。

子任务一：二分查找

解决子问题一的最简单的方法是，我们从 L = N - 1 开始，依次递减选取子串的长度，并进行判断。如果发现存在长度为 L 的重复子串，就表示 L 是最长的可能长度。

但我们发现，如果字符串中存在长度为 L 的重复子串，那么一定存在长度为 L0 < L 的重复子串（选取长度为 L 的重复子串的某个长度为 L0 的子串即可），因此我们可以使用二分查找的方法，找到最大的 L。

子任务二：Rabin-Karp 字符串编码

我们可以使用 Rabin-Karp 算法将字符串进行编码，这样只要有两个编码相同，就说明存在重复子串。对于选取的长度 L：

使用长度为 L 的滑动窗口在长度为 N 的字符串上从左向右滑动；

检查当前处于滑动窗口中的子串的编码是否已经出现过（用一个集合存储已经出现过的编码）；

若已经出现过，就说明找到了长度为 L 的重复子串；

若没有出现过，就把当前子串的编码加入到集合中。

C++代码

class Solution {
public:  
    //检查是针对存在重复子串 还是发生了哈希冲突
    bool check_hash(string& s, pair<int, int>& a, pair<int, int> b) {       //查看是否是真重复子串还是因为发生哈希碰撞而导致哈希值相同
        for (int i = a.first, j = b.first; i != a.second && j != b.second; ++i, ++j) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
    //检查字符串s中是否存在长度为len的重复子串，如果有则返回该子串，否则返回空字符串
    string check(string& s, int len){
        int base = 26;//二十六个字母对应二十六进制
        int mod = 1000007;//取模 避免哈希冲突

        int num = 0;
        for(int i = 0; i < len; i++)//计算出第一个len长度的哈希映射值
            num = (num * base + s[i] - 'a')%mod;
        
        unordered_map<int, pair<int, int>> seen;//存储的是哈希映射值及对应的坐标
        seen.insert({num, {0, len - 1}});

        int al = 1;//根据公式 计算出常数a的len次方
        for(int i = 1; i <= len; i++)
            al = (al * base)%mod;
        
        //遍历字符串 计算每一个长度为len的子串的哈希映射值
        for(int i = 1; i < s.size() - len + 1; i++){

            //计算长度为len的子串的哈希映射值
            num = num * base - ((s[i-1] - 'a') * al)%mod;
            while(num < 0) num += mod;
            num = (num + (s[i + len - 1] - 'a'))%mod;

            //查找是否有重复的子串
            if(seen.count(num))
                if(check_hash(s, seen[num], {i, i + len - 1}))
                    return s.substr(i, len);//如果是真的存在而不是因为哈希冲突，就返回这个子串
            seen.insert({num, {i, i + len - 1}});//如果是哈希冲突 就插入
        }
        return "";
    }

    //返回字符串s最长重复子串
    string longestDupSubstring(string s) {
        int m = s.size();
        int left = 0, right = m;
        string res = "";
        while(left < right){
            int mid = left + (right - left)/2;//二分法找到最长重复子串
            string tmp = check(s, mid);
            if(!tmp.empty()){//如果存在重复子串，就保存下来最长的一个重复子串
                res = tmp.size() > res.size() ? tmp : res;
                left = mid + 1;
            }else
                right = mid;

        }
        return res;
    }
};

最长重复子串(Rabin-Karp算法)

最长重复子串

C++代码