题目描述
对于一个字符串 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]) 的和是多少。
输入格式
输入一行包含一个由小写字母组成的字符串 S。
输出格式
输出一个整数表示答案。
数据范围
对于 20% 的评测用例,1≤n≤10;
对于 40% 的评测用例,1≤n≤100;
对于 50% 的评测用例,1≤n≤1000;
对于 60% 的评测用例,1≤n≤10000;
对于所有评测用例,1≤n≤100000。
样例
输入样例:
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
思路解释
附加一张别人的图
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
int last[26];//记录每个字母最后出现的位置last[i]=j,i最后出现的位置是j
int main(){
string s;
cin>>s;
int n=s.length();
s=' '+s;//前面加一个空格,下标要从1开始,若从0开始,last默认则为0会发生错误
ll res=0;//int会爆
for(int i=1;i<=n;i++){//先计算后更新last位置
res+=(ll)( n - i + 1 )*( i - last[s[i]] );
last[s[i]]=i;
}
cout<<res<<endl;
return 0;
}