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 mainimport "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代码]()