力扣 1044. 最长重复子串

题目来源：https://leetcode-cn.com/problems/longest-duplicate-substring/

大致题意：
给一个字符串 s，找出子串中出现次数超过一次的最长子串

思路

遍历 1 ~ n-1 长度的所有子串，判断是否出现次数超过一次

可以知道，如果长度为 L 的子串出现次数超过一次，那么显然该子串的子串出现次数一定也超过一次。那么当有长度为 L 的子串重复出现时，此时就只用在 L+1 ~ n-1 长度中寻找是否有重复子串，也就是可以使用二分来优化遍历

由于本地的字符串长度最大为 3 * 10⁴，所以不能直接用哈希表存子串来判断是否重复，可以用 Rabin-karp 算法对固定长度的字符串进行编码，编码相同就表示字符串相同

Rabin-karp

1. 首先将字符串转化为整数数组，每一位都减去 ‘a’
2. 将数组看成一个 x 进制的数，求出这个数。所求数可能过大，需要取模

简单地说，就是自定义了一个哈希函数，把字符串映射到为一个长整型数，由于可能存在哈希碰撞，这里需要使用双哈希，具体看代码

代码 ：

public String longestDupSubstring(String s) {
        Random random = new Random();
        // 随机两个进制，用于自定义哈希函数
        int a1 = random.nextInt(75) + 26;
        int a2 = random.nextInt(75) + 26;
        // 随即两个模
        int mod1 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int mod2 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int n = s.length();
        int[] arr = new int[n];
        // 将字符串转为为整数数组
        for (int i = 0; i < n; i++) {
            arr[i] = s.charAt(i) - 'a';
        }
        int start = -1;
        int len = 0;
        int left = 1;
        int right = n - 1;
        // 二分查找最大长度的重复子串
        while (left <= right) {
            int mid = (left + right) / 2;
            // 判断当前长度是否存在重复子串
            int idx = check(arr, a1, a2, mid, mod1, mod2);
            // 存在，更新答案，去更长的子串中判断
            if (idx != -1) {
                left = mid + 1;
                start = idx;
                len = mid;
            } else {
                // 不存在，长度过长，去短子串中判断
                right = mid - 1;
            }
        }
        // 返回对应的子串
        return start == -1 ? "" : s.substring(start, len + start);
    }
    // 检查是否存在长度为 len 的重复子串
    public int check(int[] arr, int a1, int a2, int len, int mod1, int mod2) {
        int n = arr.length;
        // a1 的 len 次方
        long base1 = pow(a1, len, mod1);
        long base2 = pow(a2, len, mod2);
        long h1 = 0;
        long h2 = 0;
        // 从首字符开始，取长度为 len 的子串，编码为长整数
        for (int i = 0; i < len; i++) {
            h1 = (h1 * a1 % mod1 + arr[i]) % mod1;
            h2 = (h2 * a2 % mod2 + arr[i]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
        }
        // 使用哈希表来判断对应编码是否出现过
        Set<Long> seen = new HashSet<>();
        // 将编码处理后放入哈希表
        seen.add(h1 * mod2 + h2);
        for (int i = 1; i <= n - len; i++) {
            // 滑动窗口，更新字符串对应编码
            // 减去最高位字符对应的数，其它位乘上进制数，再加上新字符
            h1 = (h1 * a1 % mod1 - arr[i - 1] * base1 % mod1 + arr[i + len - 1]) % mod1;
            h2 = (h2 * a2 % mod2 - arr[i - 1] * base2 % mod2 + arr[i + len - 1]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
            // 如果存在，返回重复子串对应的开始索引
            if (seen.contains(h1 * mod2 + h2)) {
                return i;
            } else {    // 不存在，放入哈希表
                seen.add(h1 * mod2 + h2);
            }
        }
        // 没有长度为 len 的重复子串，返回 -1
        return -1;
    }
    // 快速幂
    public long pow(int a, int n, int mod) {
        long ans = 1;
        // 基数
        long contribute = a;
        while (n > 0) {
            if (n % 2 == 1) {
                ans = ans * contribute % mod;
                if (ans < 0) {
                    ans += mod;
                }
            }
            contribute = contribute * contribute % mod;
            if (contribute < 0) {
                contribute += mod;
            }
            n >>= 1;
        }
        return ans;
    }