1
class Solution {
2
  public long[] hsh, hsh2, pw, pw2;
3
  public int mod = (int) 1e9 + 7;
4

5
  public long sumScores(String s) {
6
    int n = s.length(), base = 131, base2 = 137;
7
    hsh = new long[n + 1];
8
    pw = new long[n + 1];
9
    hsh2 = new long[n + 1];
10
    pw2 = new long[n + 1];
11
    pw[0] = 1;
12
    pw2[0] = 1;
13
    for (int j = 1; j <= n; j++) {
14
      hsh[j] = (hsh[j - 1] * base + s.charAt(j - 1)) % mod;
15
      pw[j] = pw[j - 1] * base % mod;
16
      hsh2[j] = (hsh2[j - 1] * base2 + s.charAt(j - 1)) % mod;
17
      pw2[j] = pw2[j - 1] * base2 % mod;
18
    }
19
    // binary search for score
20
    long ans = 0;
21
    for (int i = n; i >= 1; i--) {
22
      if (s.charAt(i - 1) != s.charAt(0)) continue;
23
      int lo = 0, hi = n - i + 1, res = 0;
24
      while (lo <= hi) {
25
        int mid = (lo + hi) >> 1;
26
        if (getSubstrHash(0, mid) == getSubstrHash(i - 1, i + mid - 1)) {
27
          lo = mid + 1;
28
          res = mid;
29
        } else hi = mid - 1;
30
      }
31
      ans += res;
32
    }
33
    return ans;
34
  }
35

36
  public long getSubstrHash(int l, int r) {
37
    long h1 = (hsh[r] - hsh[l] * pw[r - l] % mod + mod) % mod;
38
    long h2 = (hsh2[r] - hsh2[l] * pw2[r - l] % mod + mod) % mod;
39
    return (h1 << 31) | h2;
40
  }
41
}