atcoder#ARC130A. [ARC130A] Remove One Character

[ARC130A] Remove One Character

题目描述

長さ N N の文字列 S S が与えられます。 1 i N 1\leq\ i\leq\ N に対して、S S からその i i 文字目を削除してできる文字列を Si S_i と表します。

整数の組 (i,j) (i,j) であって、次の条件をともに満たすものの個数を求めてください。

  • 1 i < j N 1\leq\ i\ <\ j\leq\ N
  • Si = Sj S_i\ =\ S_j

输入格式

入力は以下の形式で標準入力から与えられます。

N N S S

输出格式

答えを出力してください。

题目大意

给定长度为NN的字符串SS1 iN1\leq\ i\leq\NSi表示为iS_i表示为i

整数组ij(i,j),请计算满足以下条件的个数:

  • 1 i < j N 1\leq\ i\ <\ j\leq\ N
  • Si = Sj S_i\ =\ S_j
7
abbbcca
4
4
xxxx
6
2
pp
1
2
st
0

提示

制約

  • 2 N 3× 105 2\leq\ N\leq\ 3\times\ 10^5
  • S S は英小文字からなる長さ N N の文字列である

Sample Explanation 1

Si S_i は、順に以下の文字列となります:bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc 条件を満たす (i,j) (i,j) は以下の 4 4 個です。 - (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)