Distinct Echo Substrings LeetCode solution in C++

1
class Solution {
2
 public:
3
  static const int N = 2005;
4
  int mod = 1e9 + 7;
5
  int B = 31;
6
  long long h[N], p[N], invp[N];
7
  int modexp(int x, int y) {
8
    int res = 1;
9
    while (y > 0) {
10
      if (y & 1) res = ((long long)res * x) % mod;
11
      x = ((long long)x * x) % mod;
12
      y = y >> 1;
13
    }
14
    return res;
15
  }
16
  int sub_hash(int l, int r) {
17
    int ans = h[r];
18
    if (l > 0) ans = ((ans + mod - h[l - 1]) * invp[l] * 1LL) % mod;
19
    return ans;
20
  }
21
  int distinctEchoSubstrings(string text) {
22
    set<int> res;
23
    int ans = 0;
24
    p[0] = 1;
25
    invp[0] = 1;
26
    for (int i = 1; i < 2005; i++) {
27
      p[i] = (p[i - 1] * B) % mod;
28
    }
29
    for (int i = 1; i < N; i++) {
30
      invp[i] = (invp[i - 1] * modexp(B, mod - 2)) % mod;
31
    }
32
    int n = text.size();
33
    h[0] = (text[0] - 'a' + 1);
34
    for (int i = 1; i < n; i++) {
35
      h[i] = (h[i - 1] + ((text[i] - 'a' + 1) * p[i]) * 1LL) % mod;
36
    }
37
    for (int len = 1; len <= n / 2; len++) {
38
      for (int i = 0; i < n + 1 - 2 * len; i++) {
39
        int a = sub_hash(i, i + len - 1);
40
        int b = sub_hash(i + len, i + 2 * len - 1);
41
        if (a == b) {
42
          if (res.find(a) == res.end()) {
43
            res.insert(a);
44
            ans++;
45
          }
46
        }
47
      }
48
    }
49
    return ans;
50
  }
51
};