自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 21:16:38，当前版本为作者最后更新于2024-09-13 13:34:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 9 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

定义一个字符串是“好的”，当且仅当这个字符串的首尾字母相同，要求出所给字符串 $s$ 的“好的”子串数量。

题目分析

本题考察简单字符串处理。

记 $n$ 为字符串 $s$ 的长度。

最直观的做法是枚举 $s$ 的每一个子串的首尾位置 $l,r(l\le r)$，若 $s_l=s_r$，则该子串是“好的”，将记录答案的变量 $ans$ 加一，最后输出 $ans$ 即可，时间复杂度为 $O(n^2)$。

还有一种做法是：用一个数组记录每一种字符在 $s$ 中出现的次数，接着枚举每一个小写字母，若它在 $s$ 种出现的次数为 $x$，则它对答案的贡献为 $\frac{x\times(x-1)}{2}$。然后由于每一个单独的字母也是“好的”，所以最终答案还应加上 $n$，时间复杂度为 $O(n)$。