Manacher算法(最长回文子串)
**Manacher算法(最长回文子串)**
**题目描述**
给定一个字符串,求其最长回文子串(Longest Palindromic Substring)。例如,字符串 "babad" 的最长回文子串为 "bab" 或 "aba"。要求算法的时间复杂度优化至 O(n)。
---
### **1. 问题分析**
暴力解法需要枚举所有子串(O(n²))并检查是否回文(O(n)),总复杂度 O(n³)。优化后可通过中心扩展法(从每个字符或间隙向两侧扩展)将复杂度降至 O(n²
2025-11-07 06:13:13
0