题解 | #密码截取#

#include<bits/stdc++.h>
using namespace std;
/*
//遍历字符串每个位置，都可以作为回文子串的中心
int main(){
    string str;
    getline(cin,str);
    int len=str.size();
    int count=0;
    for(int i=1;i<len;i++){
        //计算以i-1和i为中心的偶数长度的回文子串长度
        int low=i-1,high=i;
            while(low>=0&&high<len&&str[low]==str[high]){
                 low--;
                 high++;
                }
        count=max(count,high-low-1);
        //计算以i为中心的奇数长度的回文子串长度
        low=i-1,high=i+1;
            while(low>=0&&high<len&&str[low]==str[high]){
                low--;
                high++;
            }
        count=max(count,high-low-1);           
    }
    cout<<count<<endl;
    return 0;
}*/
//动态规划法
int main(){
    string str;
    getline(cin,str);
    int len=str.size();
    vector<vector<bool> > dp(len,vector<bool>(len,false));//dp[j][i]=1表示从j到i是回文子串
    int count=1;//初始为1
    for(int i=0;i<len;i++){
        for(int j=0;j<=i;j++){
            if(i==j)//奇数长度子串
                dp[j][i]=true;
            else if(i-j==1)//偶数长度子串
                dp[j][i]=(str[i]==str[j]);
            else
                dp[j][i]=(str[i]==str[j]&&dp[j+1][i-1]);//
            if(dp[j][i]&&i-j+1>count)
                count=i-j+1;
        }   
    }
    cout<<count<<endl;
return 0;
}