题目的主要信息：

• 输入一个长度不超过2500的字符串
• 找到其中最长的回文子串长度

方法一：中心扩散法

具体做法：

我们可以遍历每个字符串每个位置，都以其为回文子串的中心，或是奇数长度子串的中心（从两边开始找），或是偶数长度的子串中心（以它左边和它一起），分别向两边扩散，只要这个过程中两边字符是相等的就可以继续，直到边界或者不相等，这就是以这个为中心的回文子串的长度，我们比较每一个中心找到最长即可。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    string s;
    while(cin >> s){
        int maxlen = 0;
        for(int i = 1; i < s.length(); i++){ //每个点都可以为中心
            //计算以i-1和i为中心的偶数长度的回文子串长度
            int low = i - 1, high = i;
            while(low >= 0 && high < s.length() && s[low] == s[high]){ //中心两边必须都相同
                low--;
                high++;
            }
            maxlen = max(maxlen, high - low - 1); 
            //计算以i为中心的奇数长度的回文子串长度
            low = i - 1, high = i + 1;
            while(low >= 0 && high < s.length() && s[low] == s[high]){ //中心两边必须都相同
                low--;
                high++;
            }
            maxlen = max(maxlen, high - low - 1);
        }
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，外循环遍历每个点，内循环最坏情况下遍历半个字符串长度
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：动态规划

具体做法：

我们用二维数组构建子串回文情况，其中$dp[j][i]=1dp[j][i]=1$表示从$jj$到$ii$满足回文子串的要求，则有转移方程：

第一种情况是看以这个位置为中心的奇数长度的回文子串，第二种情况是以这两个位置为中心的偶数长度回文子串，第三种情况是这是边界，看中间是否是回文子串。最后找到最大的$ii$与$jj$的距离即可。

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

int main(){
    string s;
    while(cin >> s){
        int n = s.length();
        vector<vector<bool> > dp(n, vector<bool>(n, false)); //dp[j][i]=1表示从j到i是回文子串
        int maxlen = 1; //初始为1
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(i == j) //奇数长度子串
                    dp[j][i] = true;
                else if(i - j == 1) //偶数长度子串
                    dp[j][i] = (s[i] == s[j]);
                else
                    dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]); //这两个字符相等，同时中间缩也要相等
                if(dp[j][i] && i - j + 1 > maxlen) //取最大
                    maxlen = i - j + 1;
            }
        }
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，遍历二维数组
• 空间复杂度：$O(n^2)O(n^2)$，辅助空间为二维数组