最长回文子串

字符串

说明

以每个字符和字符间隙为中心向外扩展；时间 O(n²)。扩展过程只使用常数个变量，但本例先构造 []rune(s)，整体额外空间为 O(n)，n 为 rune 数量。

分析

回文中心既可能是一个字符，也可能位于两个字符之间，因此每个位置尝试奇数和偶数两类中心。两侧字符相等时继续扩张，并记录最长范围。

图解推演

对“你好吗好你”，以“吗”为中心，两侧先是“好/好”，再是“你/你”，得到长度 5 的回文。偶数回文如 abba 的中心在两个 b 之间，若只检查单字符中心便会漏掉。每次扩展以 rune 下标为单位，返回子串时也要保持相同的索引单位。

查看图表代码

适用前提与边界

示例先转成 rune，能正确处理多字节字符；超大输入可改用线性时间的 Manacher 算法。

示例输入与调用

fmt.Println(LongestPalindrome("你好吗好你"))

运行输出

你好吗好你

完整 Go 示例

package main

import "fmt"

func LongestPalindrome(s string) string {
	chars := []rune(s)
	start, length := 0, 0
	for c := 0; c < 2*len(chars)-1; c++ {
		l, r := c/2, c/2+c%2
		for l >= 0 && r < len(chars) && chars[l] == chars[r] {
			if r-l+1 > length {
				start, length = l, r-l+1
			}
			l--
			r++
		}
	}
	return string(chars[start : start+length])
}

func main() {
	fmt.Println(LongestPalindrome("你好吗好你"))
}