![在这里插入图片描述](https://img-blog.csdnimg.cn/50a96e03417f4c7c80351bba2caee0af.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56iL5bqP5aqbSkQ=,size_20,color_FFFFFF,t_70,g_se,x_16)
![在这里插入图片描述](https://img-blog.csdnimg.cn/597d3e762ffe4ed2b382d941ffc536d5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56iL5bqP5aqbSkQ=,size_20,color_FFFFFF,t_70,g_se,x_16)
一、暴力解:O(N^3)
#include<iostream>
#include<string>
using namespace std;
//判断是否为回文串
bool is_palindrome(string s){
if(s.size() == 1){
return true;
}
int i = 0;
int j = s.size()-1;
while(i < j){
if(s[i] != s[j]){
return false;
}
i++;
j--;
}
return true;
}
int main(){
string s;
cin >> s;
int max_len = 0;
for(int i = 0; i < s.size(); i++){
for(int j = 1; j <= s.size()-i; j++){
string subs = s.substr(i,j);
if(is_palindrome(subs) && j > max_len){
max_len = j;
}
}
}
cout << max_len;
}
二、中心扩散法:O(N^2)
#include<iostream>
#include<string>
using namespace std;
int getlen(string s, int l, int r){//中心扩散求回文串长度
while(l >=0 && r <= s.size() && s[l] == s[r]){
l--;
r++;
}
return r - l - 1;
}
int main(){
string s;
cin >> s;
int max_len = 0;
if(s.size() == 1){
cout << 1;
}
for(int i = 0; i < s.size(); i++){
int singles = getlen(s,i,i);//单中心ABA
int doubles = getlen(s,i,i+1);//双中心 ABBA
max_len = max(max(singles,doubles), max_len);// 中心扩展法(单双中心取最大)
}
cout << max_len;
}