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

原创

福大大架构师每日一题

发布于 2021-12-22 15:16:04

2160

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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