贡献法求解字串分值和(c++实现)

本文主要是介绍贡献法求解字串分值和(c++实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

对于一个字符串 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。

---

输出格式
输出一个整数表示答案。

#include<iostream>
#include<string.h>
using namespace std;
const int N = 100010;
char s[N];
int l[N],p[33];int main(){scanf("%s",s+1);int n = strlen(s+1);for(int i=1;i<=n;i++){int t = s[i]-'a';l[i] = p[t];p[t] = i;}long long res = 0;for(int i=1;i<=n;i++){res += (long long)(i-l[i])*(n-i+1);}printf("%lld",res);
}

这篇关于贡献法求解字串分值和(c++实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---