给定一个字符串，求出其最长回文子串。例如：
- s="abcd"，最长回文长度为 1；
- s="ababa"，最长回文长度为 5；
- s="abccb"，最长回文长度为 4，即bccb。
以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为$O(n^2)$，效率很差。
1975年，一个叫Manacher的人发明了一个算法，Manacher算法（中文名：马拉车算法），该算法可以把时间复杂度提升到$O(n)$。下面来看看马拉车算法是如何工作的。
给定一个字符串，求出其最长回文子串。例如：
以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为$O(n^2)$，效率很差。
1975年，一个叫Manacher的人发明了一个算法，Manacher算法（中文名：马拉车算法），该算法可以把时间复杂度提升到$O(n)$。下面来看看马拉车算法是如何工作的。