2021-02-06:假设字符串str长度为N,请问最长回文子串的长度是多少?
【摘要】 福哥答案2021-02-06:1.动态规划。无代码,见图。2.中心扩展法。无代码。3.Manacher算法。有代码,见图。1)理解回文半径数组。2)理解所有中心的回文最右边界R,和取得R时的中心点C。3)理解 L…(i`)…C…(i)…R 的结构,以及根据i’回文长度进行的状况划分。4)每一种情况划分,都可以加速求解i回文半径的过程。代码用的是第3种方法,用golang编写,代码如下:...
福哥答案2021-02-06:
1.动态规划。无代码,见图。
2.中心扩展法。无代码。
3.Manacher算法。有代码,见图。
1)理解回文半径数组。
2)理解所有中心的回文最右边界R,和取得R时的中心点C。
3)理解 L…(i`)…C…(i)…R 的结构,以及根据i’回文长度进行的状况划分。
4)每一种情况划分,都可以加速求解i回文半径的过程。
代码用的是第3种方法,用golang编写,代码如下:
```go
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代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class28/Code01_Manacher.java)
[力扣5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/)
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)