试题 H: 子串分值和
时光限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
【问题描述】
对于一个字符串 S，我们定义 S 的分值 f(S ) 为 S 中出现的不合的字符个
数。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。
如今给定一个字符串 S [0…n 1]（长度为 n），请你计算对于所有 S 的非空
子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是若干。

【输入格局】

输入一行包含一个由小写字母构成的字符串 S。

【输出格局】

输出一个整数表示谜底。

【样例输入】

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

【评测用例范围与商定】
对于 20% 的评测用例，1 ≤ n ≤ 10；
对于 40% 的评测用例，1 ≤ n ≤ 100；
对于 50% 的评测用例，1 ≤ n ≤ 1000；
对于 60% 的评测用例，1 ≤ n ≤ 10000；
对于所有评测用例，1 ≤ n ≤ 100000。

思路:
以ababc为例
定义一个数组存放每个字母出现的次数,len表示不是0的字母的个数
第一次for轮回大年夜左往右
那么每拜访一个字符,次数++

当前串状况alen = 1 ,a = 1ablen = 2 ,a = 1, b = 1abalen = 2 , a = 2, b = 1abablen = 2 ,a = 2, b = 2ababclen = 3 , a = 2, b = 2, c = 1

接下来,for轮回大年夜左到右,然则删除字符串最左边的值

当前串状况babca-- , len = 3 a = 1, b = 2, c = 1abcb-- , len = 3 a = 1, b = 1, c = 1bca-- , len = 2 a = 0, b = 1, c = 1cb-- ,len = 1 a = 0, b = 0, c = 1

由此可见,两次轮回下去只用O(2N)的时光求出来大年夜量的须要累加的字符串

然则ababc中心的子串bab以及以此为基本的字串都没有被推敲到,所以此时,只须要在外层新加一财揭捉环,l=0,r = str.length() ,只要l<r,就轮回,然后l++,r- -,最后就能推敲到所有的情况
代码:

因为今天刚考完担心被查重体系误判,故放下图片,不放源码,同理,不包管代码精确:


弥补一下,我测验测验生成了一个长度为10的4 次方的数据运行代码,可以1s内出现谜底,然则换成10的5次方的数据就不可了,而正常的暴力解轨则对于10的3次方就是极限,10的四次方长度的字符串则运行不出结不雅.