1.题目基本信息

1.1.题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

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

1.2.题目地址

https://leetcode.cn/problems/shortest-palindrome/description/

2.解题方法

2.1.解题思路

Manacher中心扩展算法

2.2.解题步骤

第一步，重构字符串，在每俩个字符之间插入#，首尾分别插入^和$；加#是为了解决奇偶性的问题，^和$为了避免中心扩展时超出字符串范围的问题

第二步，遍历循环s1[1:-1]（去除了首尾部分）。维护p数组，p[i]为s1[i]为中心的最长回文串的半径（默认为1）；center和right维护当前右边界最大的回文串的中心位置和右边界位置。在遍历过程中，首先初始化i处的半径，用关于center对称的位置的已知状态初始化当前的状态，分为right>i、i处关于center的对称树超过right边界、i处关于center的对称树没有超过right边界三种情况；然后进行中心扩展；最后更新center和right的变量。由于#的关系，p[1:-1]除2下取整的和即为题解。

• 2.1.初始化半径

• 2.2.中心扩展

• 2.3.更新center和right变量，以及结果变量

3.解题代码

python代码

class Solution:
    # 思路：Manacher中心扩展算法
    def countSubstrings(self, s: str) -> int:
        # 第一步，重构字符串，在每俩个字符之间插入#，首尾分别插入^和$；加#是为了解决奇偶性的问题，^和$为了避免中心扩展时超出字符串范围的问题
        s1 = "^#"
        for c in s:
            s1 += c
            s1 += "#"
        s1 += "$"
        # 第二步，遍历循环s1[1:-1]（去除了首尾部分）。维护p数组，p[i]为s1[i]为中心的最长回文串的半径（默认为1）；center和right维护当前右边界最大的回文串的中心位置和右边界位置。在遍历过程中，首先初始化i处的半径，用关于center对称的位置的已知状态初始化当前的状态，分为right>i、i处关于center的对称树超过right边界、i处关于center的对称树没有超过right边界三种情况；然后进行中心扩展；最后更新center和right的变量。由于#的关系，p[1:-1]除2下取整的和即为题解。
        length = len(s1) - 2
        p = [1] * (len(s1) - 1)     # 维护以s[i]为回文串中心的最大半径
        center, right = 0, 0        # 维护当前右侧边缘最大的回文串的中心和右侧最大
        result = 0
        for i in range(1, len(s1) - 1):
            # 2.1.初始化半径
            p[i] = min(right - i + 1, p[2 * center - i]) if right > i else 1
            # 2.2.中心扩展
            while s1[i + p[i]] == s1[i - p[i]]:
                p[i] += 1
            # 2.3.更新center和right变量，以及结果变量
            if i + p[i] - 1 > right:
                center, right = i, i + p[i] - 1
            result += p[i] // 2
        return result

4.执行结果