网站备案 人工审核,安卓软件下载安装,网站描述标签,网络科技公司都是干嘛的试题 H: 子串分值 时间限制: 1.0s 内存限制: 512.0MB 本题总分#xff1a;20 分
【问题描述】 对于一个字符串 S#xff0c;我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如 f(“aba”)1#xff0c;f(“abc”)3, f(“aaa”)0。
现在给定一个字符串 S[0…n-1]…试题 H: 子串分值 时间限制: 1.0s 内存限制: 512.0MB 本题总分20 分
【问题描述】 对于一个字符串 S我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如 f(“aba”)1f(“abc”)3, f(“aaa”)0。
现在给定一个字符串 S[0…n-1]长度为 n请你计算对于所有 S 的非空子串 S[i…j] (0ijn)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% 的评测用例1n10 对于 40% 的评测用例1n100 对于 50% 的评测用例1n1000 对于 60% 的评测用例1n10000 对于所有评测用例1n100000。 【思路】 ①暴力会超时 ②只有当字母出现的次数为1才有贡献度因此我们只需要计算出每个位置的贡献度累加求和即为答案。例如ababc如果我们求第二个位置b的贡献度则以b为中心向两边扩散找到只有一个b时的最长子串向左步长为left1即ababc向右步长为right1即ababc,所以我们找到的子串为aba它一共有ab,aba,b,ba 4种组合从左到b做起点从b到右做终点即贡献度(left1)*(right1)。
【Java代码】
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String inputString scanner.next();long res 0;for (int i 0; i inputString.length(); i) {int left 0, right 0;//统计左右步长while(i-left 0 inputString.charAt(i-left-1) ! inputString.charAt(i)) left;while (iright1 inputString.length() inputString.charAt(iright1) ! inputString.charAt(i)) right;res (1left)*(1right);}System.out.println(res);}
}
