LeetCode 5 最长回文子串--Manacher算法

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路

本文一眼看上去可以用动态规划，解法详见下一篇博客。

动态规划复杂度是 O ( n 2 ) O(n^2) O(n2) ，看完题解后发现有更简单的解法。

Manacher算法的复杂度可以到 O ( n ) O(n) O(n)。

本文基本参考这篇的讲解，附带自己的理解

Manacher 算法

原理

Manacher的是从暴力搜索简化来的。查找最长回文串最暴力的解法就是从一个字符向两边扩张知道不相等就查下一个，依次遍历完字符串就可以了。

Manacher的原理和KMP类似，也是用一个辅助数组来省略回退。

本文的图都是从这个连接里截的，不想重新画了

算法过程

Manacher还会在原数组中均匀插入一些字符，避免在找回文中点的时候指到两个字符中间。

上图，P中记录的是回文半径，即T字符串中一个回文的长度的一半。很好理解我们最后就是要构建这么一个数组P，然后找出最大值。

这里需要几个变量来记录一下过程，具体过程还是看这个连接，这里只是记录下自己的理解。

C

是当前最大回文串的中心位置，

R

是当前最大回文串的右边界。

i

是要当前计算的字符。

i_mirror

是

i

相对于

C

的镜像位置。因为是对称的，

P[i]

可以根据

P[i_mirror]

计算出来。

当

P[i] + i

，超过

R

的时候，更新

C

和

R

到

i

和

P[i]+i

。

每次

P[i]

扩张时超过

R

，

C

就会跳到

i

。每个元素只遍历两次，复杂度 O ( n ) O(n) O(n)。

代码

func longestPalindrome(s string) string {
    var T string = preProcess(s);
    n := len(T)
    var P [2002]int;
    C := 0
    R := 0
    var i int = 0
    for i = 1; i < n - 1; i++ {
        var i_mirror = 2 * C - i
        if (R > i) {
            P[i] = R - i // 防止超出 R
            if (R - i > P[i_mirror]) {
                P[i] = P[i_mirror]
            }



        } else {
            P[i] = 0// 等于 R 的情况
        }

        // 碰到之前讲的三种情况时候，需要利用中心扩展法
        for ;T[(i + 1 + P[i])] == T[(i - 1 - P[i])]; {
            P[i]++
        }

        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i
            R = i + P[i]
        }

    }

    // 找出 P 的最大值
    maxLen := 0
    centerIndex := 0
    for i = 1; i < n - 1; i++ {
        if (P[i] > maxLen) {
            maxLen = P[i]
            centerIndex = i
        }
    }
    start := (centerIndex - maxLen) / 2 //最开始讲的求原字符串下标
    return s[start:start + maxLen]
}

func preProcess(ts string) string {
    n := len(ts)
    if (n == 0) {
        return "^$"
    }
    ret := "^"
    for i := 0; i < n; i++ {
        ret = ret + " " + string(ts[i])
    }
    ret += " $"
    return ret
}