字节跳动二面算法题 ——leecode 1044. 最长重复子串（字符串哈希、二分法）

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

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

示例 1：

输入：s = “banana”
输出：“ana”
示例 2：

输入：s = “abcd”
输出：""

字符串哈希存储字符串，二分法二分要求的最长长度的重复子串的长度，尽量取最右侧的值。
set 集合存储字符串哈希值判断是否有字符串重复，如果重复二分返回 true，否则返回 false

typedef unsigned long long ULL;
const int N = 100010, P = 131;

class Solution {
public:
    ULL p[N],h[N];
    
    int n;
    int start;
    ULL get(int l,int r)
    {
        return h[r]-h[l-1]*p[r-l+1];
    }
    bool check(int mid)
    {
        unordered_set S;
        for(int i=1; i+mid-1<=n; ++i){
            ULL k = get(i,i+mid-1);
            if(S.count(k)){
                start = i;
                return true;
            }
            S.insert(k);
        }
        return false;
    }
    string longestDupSubstring(string s) {
        
        n = s.size();

        p[0] = 1;
        for(int i=1; i<=n; ++i){
            h[i] = h[i-1] * P + s[i-1];
            p[i] = p[i-1] * P;
        }

        int l=0, r = n;
        while(l < r){  //二分长度
            int mid = l + r >> 1;
            if(check(mid)) l = mid + 1;
            else r = mid;
        }
        check(r-1);

        return s.substr(start-1,r-1);
    }
};