题解 | 密码截取

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string str;
    getline(cin, str);
    if(str.size() == 1){
        cout << 1 << endl;
        return 0;
    }
    int n = str.size();

    //定义动态数组的时候不能死心眼子 要学会灵活一点 但是好难 想不到
    vector<vector<bool>> dp(n, vector<bool>(n, false)); //dp[i][j]为真表示str[i]到str[j]的字符串是回文字符串

    //初始化：单个字符串一定是回文的
    for(int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }

    //检查长度为2的子串
    for(int i = 0; i < n-1; ++i) {
        if(str[i] == str[i+1]) {
            dp[i][i+1] = true;
        }
    }

    int max_len = 1;
    //检查长度大于2的字串
    for(int len = 3; len <= n; ++len) {
        for(int i = 0; i <= n - len; ++i) {
            int j = i + len - 1; //j是子串结束的位置
            if(str[i] == str[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
                max_len = max(max_len, len);
            }
        }
    }

    cout << max_len << endl;
    return 0;
}