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代码