时间限制: 1Sec 内存限制: 128MB 提交: 355 解决: 68
题目描述
对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 1，f (”abc”) = 3, f (”aaa”) = 0。 现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串Si…j， 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。
阅读完题目后这道题类似于我上一条发的博客(感兴趣的同学可以去看)，对于此题如何求解，我这里用到的仍是元素“贡献值”法，对于不懂什么是贡献值的同学可以翻看我前一条的博客。
当指针在字符b时(黄色是界限，区域内不能出现b，一旦出现b，则无法影响字符串)，那么所能应能影响的字符串便是ab,aba,b,ba这四个字符串
当指针指向a时，(黄色是界区域内不能出现a，一旦出现a，则无法影响字符串)，那么所能应能影响的字符串便是ba,bab,babc,a,ab,abc这六个字符串，通过这样会发现如下规律；
所以根据以上所总结的规律，可写出以下代码：
package test;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.next();
long contribute=0,hou_index=0;
for(int i=1;i=0;j--) {
if(str.charAt(i)==str.charAt(j)) {
contribute+=((i-j)*(hou_index-i+1));
break;
}
if(str.charAt(i)!=str.charAt(j) && j==0) {
contribute+=((i+1)*(hou_index-i+1));
break;
}
}
}
for(int i=str.length()-2;i>=0;i--) {
if(str.charAt(i)==str.charAt(str.length()-1)) {
contribute+=(str.length()-i-1);
break;
}
if(str.charAt(i)!=str.charAt(str.length()-1) && i==0) {
contribute+=(str.length());
break;
}
}
System.out.println(contribute);
}
}
