题目

https://leetcode.com/problems/longest-duplicate-substring/

题解

这题暴力超时，看了 Related Topics，以及 Hint，主要用到 Rolling Hash，算法叫Rabin Karp，实现上参考：https://leetcode.com/problems/longest-duplicate-substring/discuss/1132925/JAVA-Solution

class Solution {
    public static final int MUL = 31;

    public String longestDupSubstring(String str) {
        int L = 0;
        int R = str.length();
        String result = "";

        while (L < R) {
            int M = (L + R) / 2; // M is length
            if (M == 0) break;

            HashSet<Long> seen = new HashSet<>();
            long hash = initHash(str.substring(0, M));
            seen.add(hash);

            long pow = 1;
            for (int l = 1; l < M; l++) pow *= MUL;

            for (int i = 1; i <= str.length() - M; i++) {
                hash = rollingHash(pow, hash, str, i, i + M - 1);
                if (seen.contains(hash)) {
                    result = str.substring(i, i + M);
                }
                seen.add(hash);
            }

            if (result.length() == M) L = M + 1;
            else R = M;
        }
        return result;
    }

    public long initHash(String s) {
        long hash = 0;
        long mul = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            hash += s.charAt(i) * mul;
            mul *= MUL;
        }
        return hash;
    }

    public long rollingHash(long pow, long hash, String s, int i, int j) {
        return (hash - s.charAt(i - 1) * pow) * MUL + s.charAt(j);
    }
}