c++ 最长回文字串代码

在 C++ 中，寻找最长回文子串的问题通常采用动态规划（Dynamic Programming）的方法解决。下面是一个简单的 C++ 代码示例，使用了 Manacher's Algorithm 进行优化，它的时间复杂度为 O(n)：

#include <iostream>
#include <string>

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        if (s.empty()) return "";
        
        int n = s.size();
        std::string t = '#'; // 添加特殊字符，便于处理边界情况
        for (char ch : s) {
            t += ch;
        }
        t += '#';
        
        int P = 0, center = 0, maxLen = 1; // P记录已知回文中心，center记录当前回文半径
        for (int i = 1; i < n + 1; ++i) {
            int mirror = 2 * center - i; // 根据对称原理计算i位置的回文镜像
            if (i < P) {
                int len = std::min(P - i, maxLen);
                if (t[i - len] == t[mirror + len]) { // 如果左右两边字符相等
                    maxLen = len + 2; // 更新maxLen
                } else {
                    maxLen = 1; // 否则恢复到1
                }
            }
            
            while (i - maxLen >= 0 && i + maxLen < n && t[i - maxLen] == t[i + maxLen]) { // 检查并向两边扩展
                maxLen++;
            }
            if (i + maxLen > P) {
                P = i + maxLen;
                center = i;
            }
        }
        
        // 返回最长回文子串
        return s.substr(s.size() / 2 - maxLen / 2, maxLen);
    }
};

int main() {
    Solution solution;
    std::string str = "babad";
    std::cout << "Longest palindrome substring is: " << solution.longestPalindrome(str) << std::endl;
    return 0;
}

这个代码首先将原字符串 `s` 增加了特殊字符以便处理奇数长度的回文，然后通过动态维护已知的最大回文半径和回文中心，找到最长的回文子串。