Dotcpp  >  编程题库  >  蓝桥杯2020年第十一届省赛真题-子串分值
题目 2572:

蓝桥杯2020年第十一届省赛真题-子串分值

时间限制: 1s 内存限制: 128MB 提交: 1331 解决: 301

题目描述

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

输出格式

输出一个整数表示答案。

样例输入

ababc

样例输出

21

提示

样例说明:

子串f值:

a     1
ab    2
aba   1
abab  0
ababc 1
 b    1
 ba   2
 bab  1
 babc 2
  a   1
  ab  2
  abc 3
   b  1
   bc 2
    c 1

对于20% 的评测用例,1 ≤ n ≤ 10;
对于40% 的评测用例,1 ≤ n ≤ 100;
对于50% 的评测用例,1 ≤ n ≤ 1000;
对于60% 的评测用例,1 ≤ n ≤ 10000;
对于所有评测用例,1 ≤ n ≤ 100000。

标签