一、暴力法
求出每一个子串，之后判断是不是回文，找到最长的那个。求每一个子串时间复杂度O(N^2),
判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N^3)。
#include <bits/stdc++.h>
using namespace std;
string palindromic(string &s) {
int len = s.size(); //字符串长度
int maxlen = 1; //最长回文字符串长度
int start = 0; //最长回文字符串起始地址
for(int i = 0; i < len; i++) { //起始地址
for(int j = i + 1; j < len; j++) { //结束地址
int tmp1 = i, tmp2 = j;
while(tmp1 < tmp2 && s.at(tmp1) == s.at(tmp2)) { //判断是不是回文
tmp1++;
tmp2--;
}
if(tmp1 >= tmp2 && j - i + 1 > maxlen) {
maxlen = j - i + 1;
start = i;
}
}
}
return s.substr(start, maxlen);
}
int main() {
string str = "abccaacbdf";
cout << palindromic(s)<<endl;
return 0;
}
运行结果：
image.png
二、中心扩展法
中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。
若题目要求最长回文字符串，则分两种情况：长度为奇数的回文串和长度为偶数的回文串，分别进行求解；
#include <bits/stdc++.h>
using namespace std;
//中心扩展函数
string palindromic(string s, int left, int right) {
while (left >= 0 && right <= s.length() - 1 && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
int main(){
string s = "abccbd";
string result = s.substr(0, 1);
for (int i = 0; i <= s.length() - 2; i++) {
string temp = palindromic(s, i, i); //若为奇数，则左右两边都从i开始扩展
if (temp.length() > result.length()) result = temp;
temp = palindromic(s, i, i + 1); //若为偶数，则左边从i开始，右边从i+1开始扩展
if (temp.length() > result.length()) result = temp;
}
cout<<result<<endl;
return 0;
}
运行结果：
image.png
若题目仅要求最长回文字符串的长度，我们可以对字符串进行填充，填充前的解为填充后的解的长度除以2。如下图：
image.png
#include <bits/stdc++.h>
using namespace std;
//中心扩展函数
int palindromic(string str,int i){
int len = 0;
for(int k=0;i-k>=0&&i+k<str.length();k++){
if(str[i-k]==str[i+k]) len++;
else break;
}
return len-1;
}
int main(){
//对原字符串进行填充
string str = "abccbd";
for(int i=0;i<str.length();i+=2){
str.insert(i,"#");
}
str.insert(str.length(),"#");
//对每一个字符中心扩展求解，求最大长度
int maxlen = 0;
for(int i=0;i<str.length();i++){
int len = palindromic(str,i);
if(len>maxlen) maxlen = len;
}
cout<<maxlen<<endl;
return 0;
}
运行结果：
image.png
三、Manacher算法
