面试经典算法:马拉松算法,最长回文子串Golang实现

求一个字符串中最长的回文子串。

package main
import "fmt"
/*
 马拉松算法,求最长回文子串,时间复杂度:线性
*/
func main() {
 // 回文数
 str := "abcddcbadcbadcabdadacd"
 // 填充#变成奇数个元素
 strArray := make([]byte, 0, 2*len(str)+1) // 每个字符是一个byte
 for i := 0; i < len(str); i++ {
 strArray = append(strArray, str[i])
 strArray = append(strArray, '#')
 }
 fmt.Print("原始字符串:")
 for i := 0; i < len(strArray); i++ {
 fmt.Print(string(strArray[i]))
 }
 fmt.Println()
 // 每个字符的最大回文半径
 radiusLen := make([]int, len(strArray))
 // 最大回文半径的中心位置
 id := 0
 // 最大回文串的右边界
 maxIndex := 0
 // 遍历新的串
 for i := 0; i < len(strArray); i++ {
 // 如果i在最大回文串中,那么可以进行判断,加快算法效率
 if i < maxIndex {
 j := 2*id - i // j和i是id的对称点
 if radiusLen[j] < maxIndex-i {
 // j的半径被最长串包住,那么i的半径必然等于j
 radiusLen[i] = radiusLen[j]
 continue
 } else if radiusLen[j] > maxIndex-i {
 // j的半径超出了最长串,那么i的半径必然是 j-(id-radiusLen(id)) = maxIndex - i 可画图观察
 radiusLen[i] = maxIndex - i
 continue
 } else if radiusLen[j] == maxIndex-i {
 // j的半径刚刚好到达最长串边界,这时i的半径可能比j还大,循环不会退出
 radiusLen[i] = radiusLen[j]
 }
 }
 for {
 // i半径必须合理,不能超过数组界,以圆心向两边拓展,逐一比较字符是否相等
 if i-radiusLen[i] >= 0 && i+radiusLen[i] < len(strArray) && strArray[i-radiusLen[i]] == strArray[i+radiusLen[i]] {
 radiusLen[i] = radiusLen[i] + 1
 } else {
 break
 }
 }
 // 如果半径比最大串还大,换人!
 if radiusLen[i] > radiusLen[id] {
 maxIndex = i + radiusLen[i] - 1
 id = i
 }
 }
 fmt.Print("处理完最长回文子串:")
 for i := id - (radiusLen[id] - 1); i <= id+(radiusLen[id]-1); i++ {
 fmt.Print(string(strArray[i]))
 }
}

转载请注明:http://www.lenggirl.com/algorithm/mala.html

本文来自:简书

感谢作者:aside section._1OhGeD

查看原文:面试经典算法:马拉松算法,最长回文子串Golang实现

• 编辑
• 预览