/**
1. 什么是重复子串?  子串x和所有可能的子串中存在一个y[i]完全相等O(n^2)     -> 滑动窗口比较hashcode 相等 O(n)
2. 怎么找最长的?   从长到短比较找到的第一个                              -> 二分长度去找最长的        O(logn)
*/

class Solution {

    static final long MOD = Long.MAX_VALUE;
    static final long BASE = 131L;

    public String longestDupSubstring(String S) {
        if (S == null || S.length() == 0) return "";
        char[] str = S.toCharArray();
        List<Long> hashcode = new ArrayList<>();
        List<Long> power = new ArrayList<>();
        Map<Long, Integer> visit = new HashMap<>();

        hash(str, hashcode, power);
        int[] result = upperBound(str, hashcode, power, visit);
        return result[0] == -1 ? "" : S.substring(result[0], result[1] + 1);
    }

    void hash(char[] str, List<Long> hashcode, List<Long> power){
        hashcode.add(0L);
        power.add(1L);
        for (int i = 0 ; i < str.length ; i ++){
            hashcode.add((hashcode.get(i) * BASE % MOD + (long)(str[i] - 'a' + 1)) % MOD);
            power.add(power.get(i) * BASE % MOD);
        }
    }

    int[] upperBound(char[] str, List<Long> hashcode, List<Long> power, Map<Long, Integer> visit){
        int l = 1, r = str.length - 1;
        int[] answer = {-1, -1};
        while (l < r){
            int mid = l + r + 1>> 1;
            int start = check(mid, hashcode, power, str, visit);
            if (start != -1) {
                l = mid;
                answer[0] = start;
                answer[1] = start + mid - 1;
            } else {
                r = mid - 1;
            }
        }
        return answer;
    }

    int check(int len, List<Long> hashcode, List<Long> power, char[] str, Map<Long, Integer> visit){
        visit.clear();
        for (int i = 0 ; i + len - 1 < str.length ; i++){
            int j = i + len - 1;
            long hashValue = hashcode.get(j + 1) - hashcode.get(i) * power.get(j - i + 1) % MOD;
            if (visit.get(hashValue) != null)   return visit.get(hashValue);
            visit.put(hashValue, i);
        }
        return -1;
    }
}