题解 | #最长回文子串#

#include <bits/stdc++.h>
using namespace std;
bool dp[355][355];//dp[i][j]表示区间[i,j]是否为回文子串
int main(){
    string s;
    while(cin>>s){
        for(int i=0;i<s.length();i++)
            dp[i][i]=true;
        for(int i=0;i<s.length()-1;i++)
            dp[i][i+1]=(s[i]==s[i+1]);
        for(int len=3;len<=s.length();len++){//由于在计算时是通过短的子串来获得大的子串的，所以不能直接枚举i,j，必须按照长度从小到大枚举
            for(int i=0;i<s.length()-len+1;i++){
                int l=i,r=i+len-1;
                dp[l][r]=dp[l+1][r-1]&(s[l]==s[r]);
            }
        }
        int maxx=1;
        for(int i=0;i<s.length();i++)
            for(int j=i + 1;j<s.length();j++)
                if(dp[i][j])
                    maxx=max(maxx,j-i+1);
        cout<<maxx<<endl;
    }
    
    
}