2021-12-22: palindrome substring. Give you a string s, please count and return

2021-12-22： Palindrome string .

Give you a string s , Please count and return this string Palindrome string Number of .

Palindrome string Is reading the same string as reading it backwards .

Substring Is a sequence of consecutive characters in a string .

A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring .

Example 1：

Input ：s = "abc",

Output ：3,

explain ： Three palindrome strings : "a", "b", "c".

Example 2：

Input ：s = "aaa",

Output ：6,

explain ：6 Palindrome substrings : "a", "a", "a", "aa", "aa", "aaa".

Tips ：

1 <= s.length <= 1000,

s It's made up of lowercase letters .

Power button 647.

answer 2021-12-22：

Horse drawn car algorithm . Count each center and then sum .

Time complexity ：O(n).

Spatial complexity ：O(n).

The code to use golang To write . The code is as follows ：

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

The results are as follows ：

picture

Zuo Shen java Code