给定一个字符串，找出其中的最长回文子串。要求先给出常见解法，再提出一种能将时间复杂度优化到 O(n) 的解法。

回答思路

1. 能正确说明暴力或动态规划解法及其复杂度
2. 能设计出 O(n) 算法（如 Manacher）并解释核心思路
3. 能分析两种解法的时空复杂度差异
4. 对边界情况（空串、单字符、相同字符）有处理说明