1
class Solution {
2
 public:
3
  vector<int> zfunction(string s) {
4
    int n = s.size();
5
    vector<int> z(n, 0);
6
    z[0] = n;
7
    int l = 0, r = 0;
8
    for (int i = 1; i < n; ++i) {
9
      if (i <= r) z[i] = min(r - i + 1, z[i - l]);
10
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
11
      if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
12
    }
13
    return z;
14
  }
15
  long long sumScores(string s) {
16
    vector<int> z = zfunction(s);
17
    long long sum = 0;
18
    sum = accumulate(begin(z), end(z), sum);
19
    return sum;
20
  }
21
};