c++ 最长回文子串

在 C++ 中找到最长回文子串可以使用动态规划或者中心扩展算法。下面是两种方法的示例代码。

方法一：动态规划

#include <iostream>
#include <vector>

std::string longestPalindrome(std::string s) {
    int n = s.length();
    std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
    int start = 0, maxLen = 1;

    // 初始化长度为1和2的回文子串
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        if (i < n - 1 && s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }

    // 计算长度大于2的回文子串
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLen = len;
            }
        }
    }

    return s.substr(start, maxLen);
}

int main() {
    std::string s = "babad";
    std::cout << longestPalindrome(s) << std::endl;

    return 0;
}

方法二：中心扩展算法

#include <iostream>

std::string expandAroundCenter(std::string s, int left, int right) {
    int n = s.length();
    while (left >= 0 && right < n && s[left] == s[right]) {
        --left;
        ++right;
    }
    return s.substr(left + 1, right - left - 1);
}

std::string longestPalindrome(std::string s) {
    int start = 0, maxLen = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        std::string s1 = expandAroundCenter(s, i, i);
        std::string s2 = expandAroundCenter(s, i, i + 1);
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > maxLen) {
            start = i - len1 / 2;
            maxLen = len1;
        }
        if (len2 > maxLen) {
            start = i - len2 / 2 + 1;
            maxLen = len2;
        }
    }
    return s.substr(start, maxLen);
}

int main() {
    std::string s = "babad";
    std::cout << longestPalindrome(s) << std::endl;

    return 0;
}

这两种方法分别使用了动态规划和中心扩展算法来找到最长回文子串。你可以根据实际情况选择其中一种方法来解决问题。这些示例代码可以在输入字符串 "babad" 的情况下找到最长回文子串。你可以根据需要修改输入字符串来测试代码。