题目链接:
编辑
输入描述
输入一行包含一个由小写字母组成的字符串 S。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
ababc
输出
21
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
JAVA解法(通过50%,要进行快读才能那100%):
import java.util.Arrays; import java.util.Scanner; public class 子串分值 { static int num=0; public static void s(String str) { int book[]=new int [26]; int n=0; for(int i=0;i<str.length();i++) { book[str.charAt(i)-'a']++; } for(int i=0;i<book.length;i++) { if(book[i]==1) num++; } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.nextLine() ; for(int i=0 ; i<str.length() ; i++){ for(int k= i ; k<str.length() ; k++){ String res = str.substring(i , k+1); s(res); } } System.out.println(num); } }
C++解法:
#include<stdio.h> #include<string.h> #define N 100002 int main() { char s[N]; int last[26]; //记录 a~z中每个字符最后被扫描的位置,即下标 int pre[N]; //记录前面与第i个字符相同的字符的位置,即下标 int next[N]; //记录后面与第i个字符相同的字符的位置,即下标 gets(s); int k,i,l; int sum=0; //sum=sum+(i-pre[i])*(next[i]-i) l=strlen(s); //字符串长度 for(i=0; i<26; i++) //由于下标从0开始,所有字符在没出现第一次前都是 -1 last[i]=-1; for(i=0; i<l; i++) { k=s[i]-'a'; pre[i]=last[k]; //前面与第i个字符相同的字符的位置 last[k]=i; //更新字符的位置 } for(i=0; i<26; i++) //由于下标从0开始,从后面到前面,所有字符在没出现第一次前都是 l last[i]=l; for(i=l-1; i>=0; i--) { k=s[i]-'a'; next[i]=last[k]; //后面与第i个字符相同的字符的位置 last[k]=i; //更新字符的位置 } for(i=0; i<l; i++) { sum+=(i-pre[i])*(next[i]-i); //(i-pre[i])为前面与第i个字符相同的字符与s[i]的距离 //(next[i]-i)为后面与第i个字符相同的字符与s[i]的距离 } printf("%d",sum); return 0; }
Python解法:
import os import sys # 请在此输入您的代码 # 接收键盘输入 s = input() # 初始化变量储存总分值 sum_point = 0 # 进行循环遍历字符串,求每个字符的分值 for i in range(0, len(s)): # 初始化左长度 left_len = 0 # 初始化右长度 right_len = 0 # 初始化参考字符 target = s[i] # 进行左循环 flag = i - 1 while flag >= 0 and s[flag] != target: left_len += 1 flag -= 1 # 进行右循环 flag = i + 1 while flag < len(s) and s[flag] != target: right_len += 1 flag += 1 # 对总分值进行累加 sum_point += (left_len + 1) * (right_len + 1) # 打印输出 print(sum_point)