4272: Remove One Character

# Remove One Character ### 内存 1024MB ### 时间 2S ## 题目描述 给定一个长度为 $N$ 的字符串 $S$。对于每个 $1 ≤ i ≤ N$，令 $S_i$ 表示从 $S$ 中删除第 $i$ 个字符后得到的字符串。 找出满足以下两个条件的整数对$(i,j)$ 的数量： 1. $1 ≤ i < j ≤ N$ 2. $S_i = S_j$ ## 输入格式 输入$N$和$S$。 ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例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