题目详情题解（0）讨论（0）提交记录（0）

AT_arc130_a.[ARC130A] Remove One Character

入门

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的字符串 SS。对于 1≤i≤N1 \leq i \leq N，用 SiS_i 表示从 SS 中删除第 ii 个字符后得到的字符串。

请计算满足以下条件的整数对 (i,j)(i, j) 的个数：

  • 1≤i<j≤N1 \leq i < j \leq N
  • Si=SjS_i = S_j

输入格式

输入从标准输入中以如下格式给出：

NN SS

输出格式

请输出答案。

输入输出样例

  • 输入#1

    7
abbbcca

    输出#1

    4

  • 输入#2

    4
xxxx

    输出#2

    6

  • 输入#3

    2
pp

    输出#3

    1

  • 输入#4

    2
st

    输出#4

    0

说明/提示

限制条件

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • SS 是仅由小写英文字母组成的长度为 NN 的字符串

样例解释 1

SiS_i 依次为：bbbcca、abbcca、abbcca、abbcca、abbbca、abbbca、abbbcc。满足条件的 (i,j)(i, j) 有以下 44 个：

  • (i,j)=(2,3)(i, j) = (2, 3)
  • (i,j)=(2,4)(i, j) = (2, 4)
  • (i,j)=(3,4)(i, j) = (3, 4)
  • (i,j)=(5,6)(i, j) = (5, 6)

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页