题目描述

给定一个字符串，请你求出其中的最长回文子串的长度。

例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 11
。

输入格式

包含一个非空字符串。

输出格式

输出一个整数，表示给定字符串的最长回文子串的长度。

数据范围

给定字符串的长度不超过 1000

样例

输入样例：

Is PAT&TAP symmetric?
输出样例：

11

算法1

动态规划

C++ 代码

#include<iostream>
#include<string>
#include<cmath>

using namespace std;

const int N=1010;
string s;
bool dp[N][N];  //dp[i][j]：以i开头,j结尾的字符串是否为回文
int MAX=1;      //非空，最长回文子串最短为1

int main(){
    getline(cin,s);
    int len=s.length();
    for(int i=len-1;i>=0;i--){          
        for(int j=i+1;j<len;j++){       //j<i，不合法；j=i长度为1，不会超过MAX，不需判断
            if(s[i]==s[j]){
                if(j-i<=2)
                    dp[i][j]=1;
                else
                    dp[i][j]=dp[i+1][j-1];
                if(dp[i][j])
                    MAX=max(MAX,j-i+1);
            }
        }
    }
    cout<<MAX<<endl;
    return 0;
}

算法2

中心扩散

C++ 代码

#include<iostream>
#include<string>
#include<cmath>

using namespace std;

string s;
int ans=1;      //最小值为1

int main(){
    getline(cin,s);
    int len=s.length();
    for(int i=0;i<len-ans/2;i++){       //分别以第i个位置为中心向两边扩散，当i<len-ans/2时已经不可能出现比ans还大的答案了
        int l=i,r=i;
        while(r+1<len&&s[i]==s[r+1]) r++;       //相同字符合为一个中心向两边扩散
        i=r;
        while(l-1>=0&&r+1<len&&s[l-1]==s[r+1]) l--,r++; 
        ans=max(ans,r-l+1);
    }
    cout<<ans<<endl;
    return 0;
}