Longest Duplicate Substring LeetCode solution in Java

1
class Solution {
2
  public String longestDupSubstring(String s) {
3
    long[] e = new long[s.length() + 1];
4
    long h = 1;
5
    int p = 991919;
6
    long M = 957689076713L;
7
    for (int i = 0; i < e.length; i++) {
8
      e[i] = h;
9
      h = h * p % M;
10
    }
11
    int lo = 0, hi = s.length(), st = 0, end = 0;
12
    while (lo < hi) {
13
      int mid = (lo + hi + 1) >> 1;
14
      Set<Long> seen = new HashSet<>();
15
      long hash = 0;
16
      boolean ok = false;
17
      for (int i = 0; i < s.length() && !ok; i++) {
18
        hash = (hash * p + s.charAt(i)) % M;
19
        if (i >= mid) {
20
          hash = (hash - e[mid] * (s.charAt(i - mid)) % M + M) % M;
21
        }
22
        if (i >= mid - 1 && !seen.add(hash)) {
23
          end = i;
24
          st = i - mid + 1;
25
          ok = true;
26
        }
27
      }
28
      if (ok) {
29
        lo = mid;
30
      } else {
31
        hi = mid - 1;
32
      }
33
    }
34
    return lo == 0 ? "" : s.substring(st, end + 1);
35
  }
36
}