Solution for LeetCode Longest Duplicate Substring

LongestDuplicateSubstring.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;

public class LongestDuplicateSubstring {
    private static final int PRIME = java.math.BigInteger.probablePrime(15, ThreadLocalRandom.current()).intValue();

    public String longestDupSubstring(String S) {
        int left = 1;
        int right = S.length();
        String maxString = "";
        while (left < right) {
            int mid = left + (right - left) / 2;
            String res = find(S, mid);
            if ("".equals(res)) {
                right = mid;
            } else {
                maxString = res;
                left = mid + 1;
            }
        }
        return maxString;
    }

    private String find(String str, int size) {
        int base = 26;
        int rm = 1; // base ^ (size -1)
        for (int i = 1; i <= size - 1; i++) {
            rm = rm * base % PRIME;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int hash = 0; //running hash
        for (int i = 0; i < size; i++) {
            hash = (hash * base % PRIME + getCharNum(str.charAt(i))) % PRIME;
        }
        map.put(hash, new ArrayList<>());
        map.get(hash).add(0);
        for (int i = size; i < str.length(); i++) {
            hash = (hash - rm * getCharNum(str.charAt(i - size)) % PRIME + PRIME) % PRIME;
            hash = (hash * base % PRIME + getCharNum(str.charAt(i))) % PRIME;
            if (map.containsKey(hash)) {
                for (int other : map.get(hash)) {
                    if (check(str, i - size + 1, other, size)) return str.substring(other, size + other);
                }
            } else {
                map.put(hash, new ArrayList<>());
            }
            map.get(hash).add(i - size + 1);
        }
        return "";
    }

    private int getCharNum(char c) {
        return c - 'a';
    }

    private boolean check(String str, int l, int m, int size) {
        for (int i = 0; i < size; i++) {
            if (str.charAt(i + l) != str.charAt(i + m)) return false;
        }
        return true;
    }
}