假设字符串str是“abcde12344321”，在str后添加“edcba”即可变成回文串。需要添加5个字符。
解法：包含最后一个字符的manacher算法算出长度，然后str的总长度减去manacher长度，就是需要添加的字符个数。
代码用golang编写，代码如下：、
package main
import "fmt"
func main() {
str := "abcde12344321"
ret := ShortestEnd(str)
fmt.Println(ret)
}
func ShortestEnd(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
}
//修改
if R == strLen {
ret = getMax(ret, pArr[i])
break
}
}
//修改
return strLen/2 - ret + 1
}
func manacherString(s string) string {
ret := "#"
sLen := len(s)
for i := 0; i < sLen; i++ {
ret += fmt.Sprintf("%c#", s[i])
}
return ret
}
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
}
}执行结果如下：
