回文串（请你统计并返回这个字）

2021-12-22：回文子串。

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

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

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

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"，

输出：3，

解释：三个回文子串: "a", "b", "c"。

示例 2：

输入：s = "aaa"，

输出：6，

解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"。

提示：

1 <= s.length <= 1000，

s 由小写英文字母组成。

力扣647。

答案2021-12-22：

马拉车算法。每个中心求个数然后求和。

时间复杂度：O(n)。

空间复杂度：O(n)。

代码用golang编写。代码如下：

package main import "fmt" func main() { s := "moonfdd" ret := countSubstrings(s) fmt.Println(ret) } func countSubstrings(s string) int { if len(s) == 0 { return 0 } dp := getManacherDP(s) ans := 0 for i := 0; i < len(dp); i++ { ans += dp[i] >> 1 } return ans } func getManacherDP(s string) []int { str := manacherString(s) pArr := make([]int, len(str)) C := -1 R := -1 for i := 0; i < len(str); i++ { if R > i { pArr[i] = getMin(pArr[2*C-i], R-i) } else { pArr[i] = 1 } for i+pArr[i] < len(str) && i-pArr[i] > -1 { if str[i+pArr[i]] == str[i-pArr[i]] { pArr[i]++ } else { break } } if i+pArr[i] > R { R = i + pArr[i] C = i } } return pArr } func manacherString(str string) []byte { charArr := []byte(str) res := make([]byte, len(str)*2+1) index := 0 for i := 0; i != len(res); i++ { if i&1 == 0 { res[i] = '#' } else { res[i] = charArr[index] index++ } } return res } func getMin(a, b int) int { if a < b { return a } else { return b } }

执行结果如下：

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class38/Problem_0647_PalindromicSubstrings.java)