1.动态规划。无代码，见图。
2.中心扩展法。无代码。
3.Manacher算法。有代码，见图。
1）理解回文半径数组。
2）理解所有中心的回文最右边界R，和取得R时的中心点C。
3）理解 L…(i`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分。
4）每一种情况划分，都可以加速求解i回文半径的过程。
代码用的是第3种方法，用golang编写，代码如下：
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
}
}执行结果如下：
