题目内容

小蓝在研究字符串性质时定义了“呼应串”：一个非空字符串，如果它的第一个字符与最后一个字符相同，则称其为呼应串；否则称为非呼应串。

给定一个由小写字母组成的长度为 $n$ 的字符串 $s$。对于每个 $i = 1, 2, \dots, n$，考虑 $s$ 的前缀 $s[1 \dots i]$。请你对于每个前缀，计算它的所有非空连续子串中，非呼应串的个数。

数据范围：字符串长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，字符串仅由小写字母构成。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示字符串的长度。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写