题目描述

对于一个字符串 S
，我们定义 S
的分值 f(S)
为 S
中出现的不同的字符个数。

例如 f(“aba”)=2，f(“abc”)=3,f(“aaa”)=1
。

现在给定一个字符串 S[0..n−1]
（长度为 n
），请你计算对于所有 S
的非空子串 Si..j
，f(S[i..j])
的和是多少。
blablabla

样例

输入样例：
ababc
输出样例：
28
样例解释
子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3
b 1
ba 2
bab 2
babc 3
a 1
ab 2
abc 3
b 1
bc 2
c 1

blablabla

算法1

(贡献法) $O(n)

每次求得每个字符对结果的贡献值
其贡献值就是当前字母能组成的所有结果；
计算：前文不含有该字符串的数量（当前字符位置减去上一次出现的位置） 剩余所有字符。
（i-a[t]）(n-i+1)at是上一次出现的位置，+1表示计算结果时要带上当前字符

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[26];
char s[N];
int main()
{
  LL res = 0;
  scanf("%s",s+1);
  int len = strlen(s+1);

  for(int i=1;i<=len;i++)
  {
    int t = s[i]-'a';
    res += (LL)(i-a[t]) * (len-i+1);
    a[t] = i;
  }
  cout<<res<<endl;
  return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla