1044-最长重复子串

LeetCode 1044. 最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"
输出："ana"

method: 二分+字符串哈希

二分查找指定长度的子串是否重复

字符串哈希：

1. 先以一个固定的长度计算第一个子串哈希值，这样可以算出最高位的权重
2. 窗口移动，要加上一个最低位，减去一个最高位
   • 先hash * prime，表示扩大一位
   • 再减去最高位-power * (s[i-len] - 'a')
   • 最后加上最低位+(s[i] - 'a')

用unsigned可以自动取模，如果冲突了可以调整prime，改成131，13131之类的

const int prime = 31;
int check(string& s, int len) {
    unsigned long long hash = 0;
    unsigned long long power = 1;
    for (int i = 0; i < len; i++) {
        hash = hash * prime + (s[i] - 'a');
        power *= prime;
    }
    unordered_set<unsigned long long> exits{hash};  // 一开始要把第一个子串放进来
    for (int i = len; i < s.size(); i++) {
        hash = hash * prime - power * (s[i - len] - 'a') + (s[i] - 'a');
        if (exits.count(hash)) return i - len + 1;
        exits.insert(hash);
    }
    return -1;
}
string longestDupSubstring(string s) {
    int n = s.size();
    int l = 1, r = n - 1;
    int pos = -1, len = -1;
    while (l <= r) {    // 一开始可能会l=r
        int mid = l + r >> 1;
        int res = check(s, mid);
        if (res != -1) {    // mid长度的子串有重复
            pos = res;
            len = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return pos == -1 ? "" : s.substr(pos, len);
}