题解 | #密码截取#

//方法1：动态规划，从回文长度为1开始，从短到长找回文串，缺点是耗时耗空间
// #include<iostream>
// #include<string>
// #include<vector>
// using namespace std;

// int findABAlen(string s)
// {
//     int n =s.length();
//     vector<vector<int>> dp(n, vector<int>(n,0));
//     int ans=0;
//     for(int k=0;k<n;k++)
//     {
//         for(int i=0;i<n-k;i++)
//         {
//             int j =i+k;
//             if(s[i]==s[j])
//             {
//                 if(k==0 || k==1)
//                 {
//                     dp[i][j]=1+k;
//                 }
//                 else 
//                 {
//                     if(dp[i+1][j-1]!=0)
//                     {
//                         dp[i][j]=dp[i+1][j-1]+2;
//                     }
//                 }
//                 ans=max(ans,dp[i][j]);
//             }
//         }
//     }
    
//     return ans;
    
// }
    

// int main()
// {
//     string str;
//     while(getline(cin, str))
//     {
//         cout<<findABAlen(str)<<endl;
//     }
//     return 0;
// }



//方法2 改进的动态规划。
#include<iostream>
using namespace std;
#include<string>
#include<vector>
int main() {
    string str;
    while (cin >> str) {
        vector<int>dp(str.size()+1, 0);//dp记录当前位置[1,n]的最大回文字符的长度
        dp[0] = 0; dp[1] = 0;//预置max为1，即不考虑只有一个字符形成回文的情况，因此第一个字符置为0；
        int max =1;
        for (int i = 2; i < str.size() + 1; i++) {
            //当前位置i的字符的前一个字符不是回文，且 当前字符与前第二个字符相等，形成ABA回文
            if (i >= 3 && dp[i - 1] == 0 && str[i - 1] == str[i - 1 - 0 - 2]) {
                dp[i] = 3;
            }
            //如果当前字符等于 前一个字符的最长回文字符串的前一个字符，在dp[i-1]基础上加2
            //这里可以解决AA 或者 ABCBA的问题
            if (str[i - 1] == str[i - 1 - dp[i - 1] - 1]) {
                dp[i] = dp[i - 1] + 2;
            }
            //记录最长的字符串
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        cout << max << endl;
    }
}