面试真题

结论：最长回文子串可用中心扩展法（O(n^2)）或Manacher算法（O(n)）。核心要点：中心扩展以每个字符及两字符间隙为中心，向左右扩直至不匹配，记录最大长度及起点；需分别处理奇数（中心1字符）和偶数（中心2相同字符）回文。Manacher统一奇偶：向原串插入'#'如'^#a#b#a#$'，利用半径数组P和中心C、右边界R避免重复扩展，线性求解。面试常写中心扩展因易实现。示例：'babad'最长'bab'或'aba'；'cbbd'为'bb'。