题解 | #密码截取#

//bool dp[i][j]为从i到j的字符串是否回文，右上三角矩阵
//1个字符和相邻相同双字符就是回文,初始化可以先判断填上去，对角线2行填完
//从右下角，从下往上，从左往右。dp[i][j]=dp[i+1][j-1]&&s[i]==s[j];

#include <bits/stdc++.h>
using namespace std;  int main(){
    string s;
    cin>>s;
    int n=s.size(),res=1;    //res为最终结果，填矩阵时不断更新
    bool **dp=new bool*[n];    //bool dp[i][j]为从i到j的字符串是否回文，右上三角矩阵
    for(int i=0;i<n;i++){
        dp[i]=new bool[n]{0};
        dp[i][i]=1;    //单字符回文
        if(i&&s[i-1]==s[i]){
            dp[i-1][i]=1;    //相邻相同双字符就是回文,初始化可以先判断填上去，对角线2行填完
            if(res!=2){
                res=2;    //更新res
            }
        }
    }
    for(int i=n-3;i>=0;i--){    //从右下角，从下到上
        for(int j=i+2;j<n;j++){    //从左到右
            dp[i][j]=dp[i+1][j-1]&&s[i]==s[j];
            if(dp[i][j]&&res<j-i+1){
                res=j-i+1;    //更新res
            }
        }
    }
    cout<<res;
}