密码截取

密码截取

思路：

Dp 递推 ，f[i][j] 满足回文串要求 f[i + 1][j - 1] 也是回文串 同时 s[i] == s[j]。

代码：

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

int main(){
    string s;
    cin>>s;
    int n = s.size();
    vector<vector<bool>> f(n,vector<bool> (n));
    int res = 0;
    //f[i][j] 满足回文串要求 f[i + 1][j - 1] 也是回文串 同时 s[i] == s[j]
    for(int j = 0; j < n; j++){
        for(int i = 0;i <= j ; i++){
            if(i == j) f[i][j] = true;
            else if(s[i] == s[j]){
                //只有两个字母 或者满足条件
                if(i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
                //res = max(res,i - j + 1);
            }
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            if(f[i][j]) res = max(res,j - i + 1);
        }
    cout<<res;
    return 0;
}