题目描述
对于一个字符串 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
算法
【只是代码的搬运工】
因为输入对从s[0]开始,计算的公式有所改变,变成
ans+=(i+1−last[s[i]-‘a’])∗(n−i)
last[s[i]-‘a’]=i+1;
时间复杂度 O(N)
参考文献
https://blog.csdn.net/weixin_45483201/article/details/109137296?utm_source=app
C 代码
#include<stdio.h>
#include<string.h>
char s[100001];
long long int last[30];
long long int ans;
int main()
{
long long int i,n;
do{
scanf("%s",s);
}while(getchar()!='\n');
n=strlen(s);
for(i=0;i<n;i++)
{
ans+=(i+1-last[s[i]-'a'])*(n-i);
last[s[i]-'a']=i+1;
}
printf("%lld",ans);
}
我只是个渣渣(x)