分析
首先，一个完整的串肯定不是。那么考虑每一个字串，最简单的情况就是其首（或尾）的一个字符不连续，就能做出一个贡献。于是我们要预处理这个位置的前和后有无与之相同的字符了。分别记为 $a_i$ 和 $b_i$，值为 0 或 1。
但是 $O(N^2)$ 去枚举字串肯定是不能过的。考虑先枚举串首下标 $i$，如果其前有与之相同的字符（$a_i=1$），则其后组成的 $N-i$ 个字串均可以贡献。如果前方不存在相同字符，则其贡献等于后方存在相同字符的位置个数，即 $\sum_{j=i+1}^{N} b_j$。所以可以对 $b$ 进行后缀和优化。
参考代码
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
28
29
30
31
| #include <iostream>
using namespace std;
int a[1000000], b[1000000];
bool c[30];
int main() {
string s;
cin >> s;
int n = s.size();
s = " " + s;
for (int i = 1; i <= n; i++) {
a[i] = c[s[i] - 'a'];
c[s[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
c[i] = 0;
}
for (int i = n; i >= 1; i--) {
b[i] = c[s[i] - 'a'];
c[s[i] - 'a']++;
b[i] += b[i + 1];
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (a[i])
ans += n - i;
else
ans += b[i + 1];
}
cout << ans;
return 0;
}
|