题解 | #密码截取#

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    string inputstr;
    getline(cin, inputstr);
    string codestr = "";
    for(int i = 0;i<inputstr.size();++i){
        if(((inputstr[i] -'0')>=0 && (inputstr[i] -'0')<=9) || 
          ((inputstr[i] -'A')>=0 && (inputstr[i] -'Z')<=25) ||
          ((inputstr[i] -'a')>=0 && (inputstr[i] -'z')<=25)){
            codestr += inputstr[i];
        }
    }
    int maxlen = 1;
    //找最长的回文子串,必须先计算小的回文
    //动态规划
    int size = codestr.size();
    vector<vector<bool>> dp(size,vector<bool>(size,false));//
    for(int i = 0;i<size;++i){
        dp[i][i] = true;
        if(codestr[i] == codestr[i+1] && i<size-2){
            dp[i][i+1] = true;
            dp[i+1][i] = true;
        }
    }
    for(int len = 2;len<size;++len){
        for(int i = 0;i<size-len;++i){
            //子串回文，且首位相等，即为新的回文
            if(dp[i+1][i+len-1] && codestr[i] ==codestr[i+len] ){
                dp[i][i+len] = true;
                if((len+1) > maxlen){
                    maxlen = len+1;
                }
            }
        }
    }
    cout << maxlen << endl;
    //中心扩展
//     for(int i = 1;i<codestr.size();++i){
//         int left = i-1,right = i+1,len = 1;
//         while(left >=0 && right <codestr.size()){
//             if(codestr[left] == codestr[right]){
//                 --left;++right;len+=2;
//             }
//             else break;
//         }
//         maxlen = max(maxlen,len);
//     }
//     for(int i = 0;i<codestr.size();++i){
//         if(codestr[i] != codestr[i+1])continue;
//         int left = i-1,right = i+2,len = 2;
//         while(left >=0 && right <codestr.size()){
//             if(codestr[left] == codestr[right]){
//                 --left;++right;len+=2;
//             }
//             else break;
//         }
//         maxlen = max(maxlen,len);
//     }
    //cout << maxlen << endl;
    return 0;
}