侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【递推】子串分值和【蓝桥杯】

GabrielxD
2023-01-11 / 0 评论 / 0 点赞 / 172 阅读 / 373 字
温馨提示:
本文最后更新于 2023-01-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

子串分值和 - 蓝桥云课


对于一个字符串 SS,我们定义 SS 的分值 f(S)f(S)SS 中出现的不同的字符个数。例如 f(aba)=2f(abc)=3,f(aaa)=1f(“aba”) = 2,f(“abc”) = 3, f(“aaa”) = 1

现在给定一个字符串 S[0...n1]S [0...n − 1](长度为 nn),请你计算对于所有 SS 的非空子串 S[i...j](0ij<n)S [i...j](0 ≤ i ≤ j < n)f(S[i...j])f(S [i...j]) 的和是多少。

输入描述

输入一行包含一个由小写字母组成的字符串 SS

其中,1n1051 ≤ n ≤ 10^5

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

ababc

输出

28

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

方法一:递推

思路

image-20230111184603033

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s = in.readLine();
        int n = s.length();
        char[] chs = ('0' + s).toCharArray();
        int[] prevs = new int[26];
        long ans = 0L;
        for (int i = 1; i <= n; ++i) {
            int curr = chs[i] - 'a';
            ans += (long) (i - prevs[curr]) * (n - i + 1);
            prevs[curr] = i;
        }
        System.out.println(ans);
    }
}
0

评论区