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