语言月赛 202409 始终

题意分析¶

给定一个仅由小写字母组成的字符串 $s$，我们需要找出其中有多少个好的子串。

好的子串定义为：首字母与尾字母相同的子串（包括长度为 $1$ 的子串）。

注意：子串是字符串中连续的一段字符，而非子序列。

我们可以通过枚举所有子串，并判断其首尾字符是否相同的方法来统计好的子串个数。

具体地，对于每个起点位置 $i$，向右扩展到所有 $j \in [i, n-1]$，判断子串 $s[i..j]$ 的首尾字符是否相同。

如果 $s[i] = s[j]$，则该子串为“好的”。

由于每次只判断首尾字符，无需检查整个子串内容，因此判断效率较高。

初始化答案计数器 ans = 0，定义 int n = s.size()。
使用两重循环：
- 外层循环枚举起始位置 $i$。for (int i = 0; i < n; i++)。
- 内层循环枚举结束位置 $j$，范围为 $[i, n-1]$。for (int j = i; j < n; j++)。
对于每个子串 $s[i..j]$，如果 s[i] == s[j]，则将计数器加一。
最终输出计数器的值。

总共有 $\frac{n(n+1)}{2}$ 个子串。每个子串最多判断一次首尾字符是否相等。

因此整体时间复杂度为 $O(n^2)$。

空间复杂度为 $O(n)$（输入字符串占用的空间）。

对于最大数据范围 $n \leq 5000$，是可以接受的。