lc1044. 最长重复子串（字符串哈希 二分）

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

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

示例 1：

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

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

提示：

2 <= s.length <= 3 * 104
s 由小写英文字母组成

写了个kmp超时了

class Solution {
    String res = "";
    int[] ne = new int[30010];
    public String longestDupSubstring(String s) {
        int n = s.length();
        for (int len = 1; len <= n-1; ++len) 
            for (int i = 0; len + i - 1 < n; ++i) {
                int j = len + i - 1;
                String ss = s.substring(i,j+1);
                if (matching(ss,s)) break;
            }
        return res;
    }
    public boolean matching(String a, String b) {
        int n = a.length(), m = b.length();
        a = " " + a;
        b = " " + b;
        int count = 0;
        //求next
        for (int i = 2, j = 0; i <= n; ++i) {
            while (j > 0 && a.charAt(i) != a.charAt(j+1)) j = ne[j];
            if (a.charAt(i) == a.charAt(j+1)) j++;
            ne[i] = j;
        }
        //匹配过程
        for (int i = 1, j = 0; i <= m; ++i) {
            while (j > 0 && b.charAt(i) != a.charAt(j+1)) j = ne[j];
            if (b.charAt(i) == a.charAt(j+1)) j++;
            if (j == n) {
                count++;
                if (count >= 2) break;
                j = ne[j];
            }
        }
        if (count >= 2) {
            res = a.trim();
            return true;
        }
        return false;
    }
}

字符串哈希+二分

class Solution {
    /**
    本题采用字符串哈希+哈希集合的方式处理判断是否有重复的子串
    而对于寻找最长长度的子串外面可以使用二分，因为答案具有二段性
        小于等于最大长度的子串存在
        而大于最大长度的子串不存在
     */
    long[] h,p;
    public String longestDupSubstring(String s) {
        int n = s.length();
        //P一般取131或13331，取模Q一般是2^64，所以我们只用long就行，溢出就相当于取模了
        int P = 131;
        String res = "";
        //h数组表示s的前缀和哈希，p数组时表示P进制
        h = new long[n+10]; 
        p = new long[n+10];
        p[0] = 1;
        for (int i = 0; i < n; ++i) {
            p[i+1] = p[i] * P;            //预处理p数组方便后面求子串哈希值
            h[i+1] = h[i] * P + s.charAt(i); //理解为将字符串转换P进制为前缀和数组
        }
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            String ss = check(s,mid);
            if (ss.length() != 0) l = mid;
            else r = mid - 1;
            res = res.length() < ss.length() ? ss : res;
        }
        return res;
    }
    public String check(String s, int len) {
        int n = s.length();
        String res = "";
        Set<Long> set = new HashSet<>();
        for (int i = 0; len + i - 1 < n; ++i) {
            int j = len + i - 1;
            //h[j]代表1~j的字符串哈希值，h[i]代表1~i的字符串哈希值
            //因为我们是看成P进制所以我们先要把h[i] * p[j-i+1] 转换为跟h[j]
            //同样的位数，再相减即为哈希值
            long hash = h[j+1] - h[i] * p[j-i+1];
            if (set.contains(hash)) {
                res = s.substring(i,j+1);
                return res;
            }
            set.add(hash);
        }
        return "";
    }
}