题目的主要信息：

给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。

方法一：

用maxlen维护目前找到的最长回文子串长度，暴力枚举一遍所有可能的子串，并且判断每个子串是否为回文串。判断每个子串是否为回文子串的方法是，从子串的首位同时向中心移动，边移动边比较，如果遇到有两位不同，表示它不是回文串。遍历完所有的子串后，maxlen的值即为最长回文子串的长度。

具体做法：

#include<iostream>
#include<string>

using namespace std;

bool isPlalindrome(string str, int begin, int end){ //检查子串是否是回文字符串
    while(begin <= end){//从首尾向中间移动，逐位比较
        if(str[begin++] != str[end--]){//有对称的两位不相同，表示它不是回文
            return false;
        }
    }
    return true;
}

int main(){
    string s;
    while(cin >> s){
        int maxlen = 1;
        for(int i = 0; i < s.size(); i++){ //遍历所有可能的子串
            for(int j = i; j < s.size(); j++){ 
                if(isPlalindrome(s, i, j)){ //判断当前子串是否是回文
                    int len = j-i+1;
                    if(len > maxlen){//如果当前子串长度比已知最长回文子串更长，则更新最大值
                        maxlen = len;
                    }
                }
            }
        }
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{3})$ ，isPalindrome函数的时间复杂度为 $O (n)$ ，外层还有两重for循环。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

历一遍字符串，计算每个字符为中点时能构成的最长回文串，输出最大的长度。判断字符串是否为回文串可以从中点出发向两边扩展，判断左右两侧是否相同，若相同则继续扩展；若不同，则停止扩展，计算当前的回文串长度。需要注意的是ABA式的回文串中点是一个字符，ABBA式回文串的中点是两个字符，所以我们遍历考虑每个字符当中点能构成的回文串时，这两种形式的长度都要计算。

alt

具体做法：

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

int getLen (string s, int l, int r) {
    while(l>=0&&r<=s.size()-1){//向左右扩展查找最大长度
        if(s[l]==s[r]){//s[l]==s[r]则继续扩展
            l--;
            r++;
        }else break;//s[l]不等于s[r]则查找结束
    }
    return r - l - 1;
}

// 中心扩展法（单双中心取最大）
int main () {
    string str;
    while(cin>>str){
        //处理边界情况
        if(str.size()==0){
            cout<<"0"<<endl;
            continue;
        }
        if(str.size()==1){
            cout<<"1"<<endl;
            continue;
        }
        //对于一般情况求解
        int maxLen=0;//保存最长的有效密码串的长度
        for(int i=0;i<str.size();i++){
            int len1=getLen(str,i,i);//ABA式对称
            int len2=getLen(str,i,i+1);//ABBA式对称
            len1=max(len1,len2);
            maxLen=max(maxLen,len1);//记录最大长度
        }
        cout<<maxLen<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，最坏情况下整个字符串都为相同的字符，外循环遍历整个字符串需要 $O (n)$ ，getLen需要判断n-i次
空间复杂度： $O (1)$ ，只用了常数空间。

题解 | #最长回文子串#

题目的主要信息：

方法一：

方法二：