c++ 最长回文字串

在C++中，寻找最长回文子串通常是一个经典的问题，可以采用动态规划（Dynamic Programming）的方法来解决。有一种常见的算法叫做Manacher's Algorithm，它的时间复杂度是O(n)，空间复杂度也是O(n)。这个算法通过维护一个回文半径数组，可以在遍历字符串的同时找到每个位置为中心的最长回文子串。

基本步骤包括：

1. 初始化两个变量，中心点`center`和最右边界`right`，以及一个回文半径数组`P[]`，其中`P[0] = P[1] = 0`。
2. 遍历字符串，对于每个字符`c`：
- 如果`c`位于`right`的左边，那么其回文半径可以从已知的较小半径开始计算，即`P[i] = min(right-i, P[2*center-i])`。
- 否则，从`c`开始向两边扩展，尝试更新`right`和`P[]`。
- 更新最长回文子串的信息，如果`P[i]`扩展到了`right`，则更新`center`和`right`的位置。
3. 返回`P[]`中的最大值对应的回文串长度，再根据该长度和原字符串返回最长的回文子串。