题解 | #密码截取#

#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
解题思路：
相当于找最长回文字串，中心扩展法重复次数太多了，还是用动态规划
因为可以利用之前检验串是否是回文，dp[i][j]表示s[i]到s[j]是否是回文串
是则为1，否则为0
若s[i] == s[j] 那么只要s[i+1]到s[j-1]是回文串就行
若s[i] != s[j] 那么s[i]到s[j]一定不是回文串
综上 状态转移方程为 dp[i][j] = ①dp[i+1][j-1],s[i] == s[j] ②0,s[i] != s[j] 
再考虑边界：dp[i][i] = 1(自己对自己)  
           dp[i][i+1] = (s[i] == s[i+1]) ? 1:0 (相邻两个)
用长度锚定字符可以避免状态无法转移，具体看代码
*/
int main() {
    string s;
    cin >> s;
    int len = s.length();
    int maxLen = 0;
    vector<vector<int> > dp(len,vector<int>(len,0));
    //边界
    for(int i = 0 ; i < len ; ++i){
        dp[i][i] = 1;//单个字符
        if(i < len - 1){//避免i+1越界
            if(s[i] == s[i+1]){//相邻两个字符
                dp[i][i+1] = 1;//是回文
                maxLen = 2;//长度为2
            }
        }
    }
    for(int L = 3; L <= len ; L++){
        for(int i = 0; i+L-1 < len ; i++){//i为右端点
            int j = i+L-1;//j为左端点
            if(s[i] == s[j] && dp[i+1][j-1] == 1){
                dp[i][j] = 1;
                maxLen = L;
            }
        }
    }
    cout << maxLen << endl;
}
// 64 位输出请用 printf("%lld")