4272: 满足以下两个条件的整数对 (i,j) 的数量

内存限制：1024 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

# Remove One Character ## 题目描述 给定一个长度为 $N$ 的字符串 $S$。对于每个 $1 ≤ i ≤ N$，令 $S_i$ 表示从 $S$ 中删除第 $i$ 个字符后得到的字符串。 找出满足以下两个条件的整数对$(i,j)$ 的数量： 1. $1 ≤ i < j ≤ N$ 2. $S_i = S_j$

输入

## 输入格式 输入$N$和$S$。

输出

## 输出格式 输出所求答案。

样例输入 复制 

7
abbbcca

样例输出 复制 

4

提示

## 输入输出样例 ### 输入样例1 ``` 7 abbbcca ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 4 xxxx ``` ### 输出样例2 ``` 6 ``` ### 输入样例3 ``` 2 pp ``` ### 输出样例3 ``` 1 ``` ### 输入样例4 ``` 2 st ``` ### 输出样例4 ``` 0 ``` ## 数据范围与提示 【样例1说明】 以下是按顺序的 $S_i$ 字符串：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc。 以下 $4$ 对 $(i,j)$ 满足条件： - $(i,j) = (2,3)$ - $(i,j) = (2,4)$ - $(i,j) = (3,4)$ - $(i,j) = (5,6)$ 【数据范围】 数据范围：$2 ≤ N ≤ 3 × 10^5$,$S$是一个由小写英文字母组成的长度为 $N$ 的字符串。 ## 题目来源 ARC130A
提交提交记录统计露一手!