题解 | #最长回文子串#

manacher算法，参考解题思路：https://leetcode.wang/leetCode-5-Longest-Palindromic-Substring.html

package main


//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A string字符串
 * @return int整型
 */
func getLongestPalindrome( A string ) int {
    // write code here
    tmp:=preProcess(A)
    n:=len(tmp)
    P:=make([]int,n)
    //一开始处于^，因此P[C]=0,C=0,R=0
    C,R:=0,0
    //遍历时#也遍历
    for i:=1;i<n-1;i++{
        i_mirror:=2*C-i
        if R>i{
            //i在R左侧，选择R范围内的有效值
            P[i]=min(R-i,P[i_mirror])
        }else{
            //等于R的情况
            P[i]=0
        }

        //中心扩展
        for tmp[i+1+P[i]]==tmp[i-1-P[i]]{
            //因为#的存在，此处仅+1即可表示回文串长度
            P[i]++
        }

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

    }

    maxLen:=0
    for i:=1;i<n-1;i++{
        if P[i]>maxLen{
            maxLen=P[i]
        }
    }
    
    return maxLen
}

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

func min(a,b int) int{
    res:=a
    if res>b{
        res=b
    }
    return res
}