LQ0103 子串分值【字符串】
题目来源:蓝桥杯2020初赛 C++ A组H题
题目描述
对于一个字符串S ,我们定义S 的分值f (S ) 为S 中恰好出现一次的字符个数。
例如f (”aba”) = 1, f (”abc”) = 3, f (”aaa”) = 0。
现在给定一个字符串S [0…n - 1](长度为n),请你计算对于所有S 的非空子串S [i… j](0 ≤ i ≤ j < n), 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
输出样例
21
问题分析
字符串处理问题。
AC的C++语言程序如下:
/* LQ0103 子串分值 */
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s;
long long sum = 0;
for (int i = 0; s[i]; i++) {
int l, r;
for (l = i - 1; l >= 0; l--)
if (s[l] == s[i]) break;
for (r = i + 1; s[r]; r++)
if(s[r] == s[i]) break;
sum += (i - l) * (r - i);
}
cout << sum << endl;
return 0;
}