题解 | #密码截取#

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

/*求回文子串，动态规划方程：
用双指针i j分别表示子串起点终点的索引值
dp[i][j]=true（i==j，1个字符一定是回文）
dp[i][j]=(s[i]==s[j])?（i=j-1，则只判断s[i]=s[j]与否）
dp[i][j]=(s[i]==s[j] && dp[i+1][j-1])（j>i+1，则需要判断子串是否回文，以及子串加上两端新字符是否回文）*/
int findLongestPasswd(string str){
    int max_Length=1;
    vector<vector<int>> dp(str.length(),vector<int>(str.length(),0));
    for(int i=0;i<str.length();i++){
        dp[i][i]=1;
    }

    for(int L=2;L<=str.length();L++){   //遍历每一个长度≥2的子串
        for(int j=0;j<str.length();j++){    //子串的起点
            if(L+j>str.length()){   //如果超界，直接退出循环层2
                break;
            }

            if(L==2){
                dp[j][j+L-1]=(str[j]==str[j+L-1])?1:0;
            }
            else{
                dp[j][j+L-1]=(str[j]==str[j+L-1])?dp[j+1][j+L-2]:0;
            }

            if((dp[j][j+L-1]==1)&&(L>max_Length)){
                max_Length=L;
            }
        }
    }
    return max_Length;
}

int main() {
    string str;
    cin>>str;
    int res=findLongestPasswd(str);
    printf("%d",res);
    return 0;
}
// 64 位输出请用 printf("%lld")