题解 | #最长回文子串#

首先贴一下代码：
思路大体如下：

1. 主要宗旨计算每个元素的P[i]，也就是元素i所包含的回文字符串的最大半径
2. 利用镜像的特性，去压缩后续计算量
3. 利用一个性质，由于我们提前处理了字符串，使得处理完毕的字符串都是奇数长度，这样我们就不需要调用两次expand方法。还有一点，假设原来字符串为 ”abbac“ --预处理---> "abbac"， 原来的字符串最长回文串的长度 是等于 预处理之后的P[i]的最大值的。利用这一点可以解得这道题目的最终解。
4. 预处理里面采用strings.Builder来拼接字符串可以获得最优的性能
5. p数组提前分配充足的空间，由于这里的长度是已知的；这样的好处就是避免后续由于空间不足所导致的重复分配，影响性能。
6. 该算法是manacher算法，这个算法有两点改进：第一就是避免了奇数和偶数字符串的分类讨论，用填充的手段，空间换时间；第二就是利用计算过得信息p[i], 利用i，maxRight，center，三者来压缩搜索空间，提升性能。
7. 代码部分为了美观，我统一使用英文注释，不过主要思路如上所示。
8. 大家如果对于manacher算法的改进第二点有不理解的话，也就是关于镜像如何去压缩空间。可以参考这个链接manacher算法

package main
import "strings"

func getLongestPalindrome( A string ,  n int ) int {
    // write code here
    var maxLen int
    var builder strings.Builder

    // 1. process the raw strings to get s
    builder.WriteString("*")
    for i:=0; i<len(A); i++ {
        builder.WriteString(string(A[i])+"*")
    }
    s := builder.String()

    // 2. define some variables
    // maxright means max right boundary
    // center means the corresponding center with the maxright
    maxRight, center := 0, 0

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

    // 3. computing p []int{}
    for i:=0; i<len(s); i++ {
        var finalLen int
        // cam use mirror features to decrease the space of searching for computing p
        if i < maxRight {
            mirror := 2*center - i
            tmpLen := min(p[mirror], maxRight-i)

            // further searching
            finalLen = expand(s, i-tmpLen, i+tmpLen)
        }else{
            finalLen = expand(s, i, i)
        }

        // get the p[i]
        p[i] = finalLen
        if p[i] > maxLen {
            maxLen = p[i]
        }

    }

    return maxLen

}

// expand returns length 
func expand(s string, left, right int) int {
    for ; left >=0 && right < len(s) && s[left] == s[right]; left, right = left-1, right +1 {
    }
    return (right-left-2)/2
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}