LeetCode题解:最长回文串之manacher算法

算法
总计 733 字
目录

manacher 俗称马拉车算法，也是本文的主角，是一种能够将最长回文串的求解复杂度降低到 O(N) 的一种高效算法， 当我第一次见到求解最长回文串的题目时，首先采用的就是暴力解法，O(N平方) 复杂度遍历所有可能的串，然后再用 O(N) 的时间来求回文串的最大长度，使用 map 存储各个下标对的回文情况尽管能减少一部分计算， 但是显然这种方式时间复杂度过高，部分 case 容易超时

这种算法的大概思路如下：

  • 通过插入一些符号简化奇偶个数和边界对判断回文串的干扰
  • 中心点的整个边界(除去中心点)的一半恰好等于中心点的最大回文串长度
  • 利用大回文串边界内的位置的最大回文串个数以大中心点对称的规律大大简化计算量

本人使用 Go 语言实现上述算法 详细代码如下：

// LeetCode No.5 Longest Palindromic Substring
func longestPalindrome(s string) string {
    // 方便我们后面直接使用切片操作获得结果
    origin := []byte(s)

    // 一个字母不考虑回文
    if len(origin) == 1 {
        return s
    }

    var maxCenterIndex int

    bs := process(s)
    p := make([]int, len(bs))

    c := 0
    r := 0

    for i:=1;i<len(bs)-1;i++{
        // mirror 是 i 以 c 为对称轴的对称下标
        mirror := 2*c-i

        // 当有右边界的时候
        if r > i {
            // 边界不越过大回文串的串中心的最大回文串长度与对称位置的最大回文串长度相等
            if r-i > p[mirror] {
                p[i] = p[mirror]
            } else {
                // 边界越过时 i 位置的最大回文串长度至少等于 i 到边界的长度
                p[i] = r-i
            }
        }

        // 计算位置 i 的最大回文串长度，之前的计算 p[i] 的步骤节省了大量的回文比较
        // 注意 +1 和 -1 除去自己与自身相比较的情况
        for bs[p[i]+i+1] == bs[i-p[i]-1] {
            p[i]++
        }

        // 边界扩大的时候重新计算中心点
        if i+p[i] > r {
            r = i+p[i]
            c = i
        }

        // 每一轮计算都能得到以 bs[i] 为中心的最大回文串长度，这里我们维护一个最大的即可
        if p[maxCenterIndex] < p[i] {
            maxCenterIndex = i
        }
    }

    mx := p[maxCenterIndex]

    // 由中间串的中心位置计算源串的起始位置
    startIndex := (maxCenterIndex - 1) / 2 - mx/2
    endIndex := startIndex + mx
    return string(origin[startIndex:endIndex])
}

// 使用 buffer 高效处理原串，目的是处理掉原串奇偶个数以及边界带来的问题，使算法的实现更加简洁
// eg: input - "abcabc" -> output - "^#a#b#c#a#b#c#$"
// ps: Go 1.10 版本已支持 stringBuilder
func process(s string) []byte {
    bs := []byte(s)
    var buffer bytes.Buffer
    buffer.WriteString("^")
    for _,b := range bs {
        buffer.WriteString("#")
        buffer.WriteByte(b)
    }
    buffer.WriteString("#$")
    return buffer.Bytes()
}