C++ 最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>

using namespace std;

vector<int> read_line_data();
void output_data(const vector<int>& data);

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int max_length = 0;
        int left = 0;
        int right = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j] && ((j - i + 1) >= max_length)) {
                    max_length = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        cout << left << " " << right << endl;
        return s.substr(left, right - left + 1);
    }
};

int main() {
    Solution s;
    cout << s.longestPalindrome("babad") << endl;
    return 0;
}

vector<int> read_line_data() {
    string src;
    getline(cin, src);
    istringstream iss(src);

    vector<int> data;
    int token;
    while(iss >> token) {
        data.push_back(token);
    }

    return data;
}

void output_data(const vector<int>& data) {
    int n = data.size();
    for (int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
}