题解 | #最长回文子串#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A string字符串
 * @return int整型
 */
func getLongestPalindrome(A string) int {
	n := len(A)
	t := make([]byte, n+n+1)
	t[0] = '#'
	m := 1
	for i := 0; i < n; i++ {
		t[m] = A[i]
		m++
		t[m] = '#'
		m++
	}
	maL, maR := 0, -1
	dp := make([]int, len(t))
	for i := 0; i < m; i++ {
		curL, curR, k := i, i, 1
		if i >= maL && i <= maR {
			mid := (maR + maL) / 2
			j := mid - (i - mid)
			if j-dp[j]/2 > maL {
				dp[i] = dp[j]
				continue
			} else {
				curR = maR
				k = maR - i
				curL = i - k
			}
		}
		for ; i-k >= 0 && i+k < m && t[i-k] == t[i+k]; k++ {
			curL = i - k
			curR = i + k
		}
		dp[i] = curR - curL + 1
		if dp[i] > maR-maL+1 {
			maL = curL
			maR = curR
		}
	}
	return (maR - maL) / 2
	// write code here
}