始终题解

szh_AK_all · 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)。