根据你讲的，写了段code，提交没通过，卡在了最后一些数据，老师能帮忙看下问题在哪吗？

Question

class Solution {
    long[] h;
    long[] p;
    long mod = (long)1e9+7;
    public String longestDupSubstring(String s) {
        int n = s.length();
        int P = 131;
        p = new long[n+1];
        h = new long[n+1];
        p[0] = 1;
        for(int i = 1; i <= n; i++) {
            p[i] = p[i-1] * P % mod;
            h[i] = (h[i-1] * P + s.charAt(i - 1)) % mod;
        }
        int l = 1, r = n, start = 0, length = 0;
        while(l < r) {
            int mid = l + r >> 1;
            Set<Long> set = new HashSet<>();
            for(int i = 0; i + mid <= n; i++) {
                long tmp = get(i, i + mid - 1);
                if(set.contains(tmp)) {
                    length = mid;
                    start = i;
                } else {
                    set.add(tmp);
                }
            }
            if(length == 0) r = mid;
            else l = mid + 1;
        }
        return s.substring(start, start + length);
    }
    long get(int l, int r) {
        return (h[r + 1] - h[l] * p[r-l+1] % mod + mod) % mod;
    }
}

Answer 1

javaman 2021-05-13 18:09:03

大概看了下 两个问题：

（1） length 定义在while循环， 循环里可能赋值过了，所以二分不合法时length不一定是0，可能是之前存储过的值

（2） get函数对于定长的字符串 乘的是相同的值p[r - l + 1]，这样其实和没乘一样，乘的目的是要把指数差异消掉，所以乘的值取决于字符串截取的位置——应该与子串对应多项式的最高/最低指数相关

Answer 2

javaman 2021-05-13 01:23:40

能否提供下题号？

• 提问者 qyholy #1

  1044，你课上讲的题