1044. 最长重复子串 二分 + Rabin-Karp | | 后缀数组

题目链接

Rabin-Karp算法思路：推荐Rabin-Karp算法的讲解，，力扣官方

自己的理解：Rabin-Karp形如下面的例子，这个算法能够快速的比较是否存在某个字符串，并且方便删除头一个元素，然后在尾部加入一个元素。
为什么？看下面的例子。

1123456789 字符集[1,2,3,4,5,6,7,8,9,0] 长度为10

目标串：123 = 1 * 10 ^ 2 + 2 * 10 ^ 1 + 3 * 10 ^ 0

112 : 112

123 : 123 = (112 - 1 * 10 ^ 2) + 3 * 10 ^ 0 = （112 - 100）* 10 + 3

234 : 234 = (123 - 1 * 10 ^ 2) + 4 * 10 ^ 0 = （123 - 100）* 10 + 4

345 : 345 = (234 - 2 * 10 ^ 2) + 5 * 10 ^ 0 = （234 - 200）* 10 + 5

Rabin-Karp写法，代码来自,wa_tle评论给的代码

class Solution {
    public String longestDupSubstring(String str) {
        int[] arr = new int[str.length()];
        for(int i=0; i 0) {
                left = mid;
            } else {
                right = mid-1;
            }
        }
        int start = checkRK(arr, left);
        if(start == -1) return "";
        else return str.substring(start, start + left);
    }

    final long modulus = (long)Math.pow(2,32); // 取模的模值
    final int a = 26; // 系数

    private int checkRK(int[] arr, int length) {
        long curHash = 0;
        HashSet seen = new HashSet<>();
        // 首先统计0----length-1 这个长为length的的哈希值
        for (int i=0; i

待填写