解题思路

统计 $s$ 里有多少段连续子串是回文。内容相同但起点不同的子串要分别计数。每个单字符都是回文。

回文一定关于某个中心对称。中心可以是一个字符（奇数长度），也可以是两个字符中间的缝（偶数长度）。
枚举每个中心，左右指针同时向外扩，只要 $s[left]=s[right]$ 就找到一个回文，计数加一。
一共 $2n-1$ 个中心，每个中心最多扩 $O(n)$ 步，总复杂度 $O(n^2)$ 。 $|s|\le 1000$ ，足够。
也可以 $dp[i][j]$ 表示 $s[i..j]$ 是否回文： $s[i]=s[j]$ 且内部是回文（或长度不超过 $2$ ）。常见假解：只数奇数回文；按内容去重；把子序列也算进去。

题目内容

给定一个由小写英文字母组成的字符串 $s$ ，请统计字符串 $s$ 中回文子串的数量。

回文字符串是指正着读和倒着读完全相同的字符串。

子字符串是字符串中由连续字符组成的一个序列。

需要注意的是，即使两个回文子串的内容相同，只要它们在原字符串中的位置不同，也需要分别计数。

输入一行字符串 $s$ ，表示给定的字符串。

$1 \le |s| \le 1000$

字符串 $s$ 仅由小写英文字母组成。

输出一个整数，表示字符串 $s$ 中回文子串的数量。

输入

abc

输出

说明

字符串 $s$ 中共有 $3$ 个回文子串，分别为 $a$ 、 $b$ 和 $c$ 。

因此答案为 $3$ 。

输入

aaa

输出

说明

长度为 $1$ 的回文子串共有 $3$ 个，分别对应字符串中的三个字符 $a$ 。

长度为 $2$ 的回文子串共有 $2$ 个，分别为第 $1$ 、第 $2$ 个字符组成的 $aa$ ，以及第 $2$ 、第 $3$ 个字符组成的 $aa$ 。

长度为 $3$ 的回文子串共有 $1$ 个，即 $aaa$ 。

因此回文子串总数为

$3+2+1=6$ 。

选择提交后点击「开始AI分析」