题解 | #密码截取#

思路简单的方法就是动态规划，仔细观察发现有那种“包含”的关系，那么意味着有状态转移，不过这个复杂度很高空间复杂度为O(n^2),时间复杂度也为o(n^2)

#include <string>
#include <map>
#include <vector>

using namespace std;
#define N 2500

int main() {
    string str;
    while(cin>>str){
        int n = str.size();
        bool dp[N][N]={false};
        int max=0;
        for(int j =0;j<n;j++){
            
            for(int i = 0;i<=j;i++){
                if(j-i==0)dp[i][j]=true;
                else if((j-i==1)&&(str[i]==str[j]))dp[i][j]=true;
                else if(j-i>1) dp[i][j]=dp[i+1][j-1]&&(str[i]==str[j]);
                if(dp[i][j]&&max<(j-i+1))    max = j-i+1;
            }
            
        }//外层for
        cout<<max;
    }
    
    
    
}