Longest Duplicate Substring LeetCode solution in C++

1
class Solution {
2
  using ull = unsigned long long;
3

4
 public:
5
  string longestDupSubstring(string s) {
6
    int n = s.size();
7
    vector<ull> power(n, 1);
8
    for (int i = 1; i < n; i++) {
9
      power[i] = power[i - 1] * 27;
10
    }
11
    return solve(s, power);
12
  }
13

14
  string solve(string &s, vector<ull> &power) {
15
    int low = 1, high = s.size();
16
    while (low <= high) {
17
      int mid = low + (high - low) / 2;
18
      if (check(s, mid, power) != -1) {
19
        low = mid + 1;
20
      } else {
21
        high = mid - 1;
22
      }
23
    }
24
    int start = check(s, low - 1, power);
25
    if (start > 0) return s.substr(start, low - 1);
26
    return "";
27
  }
28

29
  int check(string &s, int len, vector<ull> &power) {
30
    if (len <= 0) return -1;
31
    unordered_set<ull> st;
32
    ull curr_hash = 0;
33
    for (int i = 0; i < len; i++) {
34
      curr_hash = curr_hash + power[len - i - 1] * (s[i] - 'a');
35
    }
36
    st.insert(curr_hash);
37
    for (int i = len; i < s.size(); i++) {
38
      curr_hash = curr_hash - power[len - 1] * (s[i - len] - 'a');
39
      curr_hash = curr_hash * 27;
40
      curr_hash = curr_hash + (s[i] - 'a');
41
      if (st.count(curr_hash)) {
42
        return i - len + 1;
43
      }
44
      st.insert(curr_hash);
45
    }
46
    return -1;
47
  }
48
};