福哥答案2021-02-06：
1.动态规划。无代码，见图。
2.中心扩展法。无代码。
3.Manacher算法。有代码，见图。
1）理解回文半径数组。
2）理解所有中心的回文最右边界R，和取得R时的中心点C。
3）理解 L…(i`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分。
4）每一种情况划分，都可以加速求解i回文半径的过程。
代码用的是第3种方法，用golang编写，代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
fmt.Println("yyabcbaxxx的最长回文子串长度是：", manacher("yyabcbaxxx"))
}
func manacherString(s string) string {
ret := "#"
sLen := len(s)
for i := 0; i < sLen; i {
ret = fmt.Sprintf("%c#", s[i])
}
return ret
}
func manacher(s string) int {
str := manacherString(s)
strLen := len(str)
pArr := make([]int, strLen)
C := -1
R := -1
ret := 1
for i := 0; i < strLen; i {
if R > i {
pArr[i] = getMin(R-i, pArr[2*C-i])
} else {
pArr[i] = 1
}
for i pArr[i] < strLen && i-pArr[i] >= 0 {
if str[i pArr[i]] == str[i-pArr[i]] {
pArr[i]
} else {
break
}
}
if i pArr[i] > R {
R = i pArr[i]
C = i
}
ret = getMax(ret, pArr[i])
}
return ret - 1
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
在这里插入图片描述左神java代码
力扣5. 最长回文子串
