2021-12-22：回文子串。 给你一个字符串 s ，请你统计并返

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
    }
}