JAVA程序设计：最长重复子串（LeetCode：1044）

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

 

示例 1：

输入："banana"
输出："ana"
示例 2：

输入："abcd"
输出：""
 

提示：

2 <= S.length <= 10^5
S 由小写英文字母组成。

思路：二分长度+哈希，通过二分长度我们可以每次根据固定长度判断是否存在重复子串，而在找重复子串的过程中我们需要进一步优化，通过哈希的方法快速找到当前长度的串是否含有子串。

有一个问题是，为啥我余数用Integer.MAX.VALUE反而会造成哈希冲突？

class Solution {

    private String ans;
    static final long P = (long)(Math.pow(2,32));
    static final long BASE = 26;

    public String longestDupSubstring(String S) {

        ans = "";
        int l = 1, r = S.length();
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid, S))
                l = mid + 1;
            else
                r = mid - 1;
        }

        return ans;
    }

    private boolean check(int x, String s) {

        int len = s.length();
        Set<Long> st = new HashSet<>();
        long[] hashValue = new long[len];

        hashValue[0] = s.charAt(0) - 'a';
        for (int i = 1; i < x; i++)
            hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
        st.add(hashValue[x - 1]);
        for (int i = x; i < len; i++) {
            hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
            long val = (hashValue[i] - hashValue[i - x] * q(BASE, x) % P + P) % P;
            if (st.contains(val)) {
                ans = s.substring(i - x + 1, i + 1);
                return true;
            }
            st.add(val);
        }

        return false;
    }

    private long q(long x, long y) {
        long res = 1;
        while (y > 0) {
            if (y % 2 == 1)
                res = res * x % P;
            x = x * x % P;
            y /= 2;
        }
        return res;
    }

}

 

本文地址：https://blog.csdn.net/haut_ykc/article/details/107248926