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;
    }
}