最长回文子串（马拉车算法）
5：最长回文子串
题目：
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
输入：s = "ac"
输出："a"
解法1：中心扩展法
//将字符处理成带#的
string fillchar(string &s) {
string result = "#";
for (int i = 0; i < s.length(); i++) {
result += s[i];
result += "#";
}
return result;
}
//将字符恢复成不带#的
string restoreStr(string s, int pos, int longer) {
string result = "";
string subStep1Str = s.substr(pos - longer / 2, longer);
for (int i = 0; i < subStep1Str.size(); i++) {
if (subStep1Str[i] != '#') {
result += subStep1Str[i];
}
}
return result;
}
//中心扩展法求最长回文子串
string longestPalindrome(string str) {
string s = fillchar(str);
int arrPos[s.length()];
string longestStr = "";
for (int i = 0; i < s.length(); i++) {
int currentLong = 1;
int j = i;
int step = 1;
while (true) {
if (j == 0 || j == s.length()) {
arrPos[i] = currentLong;
break;
}
if (j - step < 0 || j + step > s.length()) {
arrPos[i] = currentLong;
break;
}
if (s[j + step] == s[j - step]) {
currentLong += 2;
step++;
} else {
arrPos[i] = currentLong;
break;
}
}
}
int maxPos = 0;
int maxLonger = 0;
for (int i = 0; i < (sizeof(arrPos) / sizeof(int)); i++) {
if (arrPos[i] > maxLonger) {
maxLonger = arrPos[i];
maxPos = i;
}
}
longestStr = restoreStr(s, maxPos, maxLonger);
return longestStr;
}
int main() {
string s = "babadada";
string result = longestPalindrome(s);
cout << "result: " << result << endl;
return 0;
}
思路分析：
思路异常简单：
1：将字符串进行处理，把原字符串"abba" ---->“#a#b#b#a#”
2：遍历字符串，检查以每个位置上的字符为中心向左右两边扩展的字符，记录以此为中心的最长回文半径和此回文中心
3：找到半径最大的回文半径和回文中心，将字符串去掉#恢复原字符，返回即可
复杂度分析：
时间复杂度：
以每个字符为中心遍历，最差的情况，字符串本身就是回文字符，平均遍历n次，所以时间复杂度为
空间复杂度：使用了有限的变量，因此空间复杂度为o(1)
解法2：Manachar（马拉车）算法
实现如下：
//处理字符串，将字符串处理成带#的
string fillchar(string &s) {
string result = "#";
for (int i = 0; i < s.length(); i++) {
result += s[i];
result += "#";
}
return result;
}
//确认pos位置上字符的最长回文半径
int findMaxRadius(const string &s ,int pos){
int step = 1;
int maxRadius = 0;
while (true){
if(pos - step <0 || pos + step > s.length()){
break;
}
if(s[pos-step] != s[pos +step]){
break;
}
step ++;
maxRadius ++;
}
return maxRadius;
}
//马拉车算法
string manacher(string str) {
string s = fillchar(str);
//回文半径数组
int radiusArray[s.length()];
//最大回文半径右边界
int rightPos = 0;
//最大回文半径右边界对应的回文中心
int centerPos = 0;
//当前位置对饮的回文半径
int currentPosMaxRadius = 1;
//最大回文半径
int maxRadius = 0;
//最大回文半径对应的回文中心
int maxRadiusCenterPos = 0;
for (int i = 0; i < s.length(); i++) {
if (i < rightPos) {
//2：如果中心点在最右边界的里面
// 找到以中心点为对称的i'点，并计算 i'点的最左回文半径所在 的位置
//2.1: i'点最左回文左区间位置 != 以centerPos为中心的左回文区间位置，
// 则 i点的回文半径为（rightPos - i）
//半径0 1 0 1 2 1 0 1 0
//下标0 1 2 3 4 5 6 7 8
//字符# c # b # b # d #
//最右0 2 2 4 6 6 6 8 8
//中心0 1 1 3 4 4 4 7 7
int ii = centerPos - (i-centerPos);
int iiRadius = radiusArray[ii] ;
int iiLeftPos = ii - iiRadius;
int centerLeftPos = centerPos - radiusArray[centerPos] ;
//情况2：
if(iiLeftPos > centerLeftPos ){
radiusArray[i] = iiRadius;
}
//2.2: i'点最左回文左区间位置没有 == 以centerPos为中心的左回文区间位置，
// 则i的回文半径需要从R+1位置计算，确定回文半径
else{
//情况3：
currentPosMaxRadius = findMaxRadius(s,i);
radiusArray[i] = currentPosMaxRadius;
rightPos = i+ currentPosMaxRadius;
centerPos = i;
}
if(currentPosMaxRadius >maxRadius){
maxRadius = currentPosMaxRadius;
maxRadiusCenterPos = i;
}
} else{
// 情况1:中心点在右边界外面
currentPosMaxRadius = findMaxRadius(s,i);
radiusArray[i] = currentPosMaxRadius;
rightPos = i+currentPosMaxRadius;
if(currentPosMaxRadius >maxRadius){
maxRadius = currentPosMaxRadius;
maxRadiusCenterPos = i;
}
centerPos = i;
}
}
//求解到最大的回文字符串
string longestPalindromeStr = "";
string temp = s.substr(maxRadiusCenterPos - maxRadius,2*maxRadius +1);
for(int i = 0;i<temp.length();i++){
if(temp[i] != '#'){
longestPalindromeStr+=temp[i];
}
}
return longestPalindromeStr;
}
思路分析：
manachar 算法是处理回文字符串的经典的算法，将时间复杂度由平方下降到常数级，并且可解决关于回文的一系列问题
1：提出了几个概念
-
回文半径，即以某个位置的字符为中心轴，向左右2个方向扩展的长度为回文半径 ps：使用manachaer算法，需要将原字符串处理成带有特殊字符的新子串
-
回文半径数组：将每一个位置上的回文半径记录成一个数组
-
当前的最右回文右边界 R /最右回文右边界对应的回文中心 C：
从左向右挨个遍历时，每一个位置都可计算出一个回文字符串的最右边的位置，最有的边界位置即为回文右边界
取得最大回文有边界时的回文中心即 最大回文边界对应的回文中心
//半径 0 1 0 1 2 1 0 1 0 //下标 0 1 2 3 4 5 6 7 8 //字符 # c # b # b # d # //最右回文边界 0 2 2 4 6 6 6 8 8 //最右边界中心 0 1 1 3 4 4 4 7 7
回计算最长回文字符串的时候只有3中情况：
-
情况1：遍历的当前位置i，i不在当前最右回文右边界之内，在最大回文有边界的右边
-
情况2：遍历的当前位置i，i在最右回文右边界的的里面，在最大回文有边界的左边，并且找到以最右回文右边界对应的回文中心点C为轴，当前位置的左对称点ii点，当ii点的回文左边界iiLeftPos在C为中心得回文子串内，即iiLeftPos 在C为中心，C的回文子串的左边界为centerLeftPos的内部，也就是iiLeftPos 在centerLeftPos的左边
-
情况3：遍历的当前位置i，i在最右回文右边界的的里面，在最大回文有边界的左边，并且找到以最右回文右边界对应的回文中心点C为轴，当前位置的左对称点ii点，当ii点的回文左边界iiLeftPos在C为中心得回文子串外面 或者边界上，即iiLeftPos 在C为中心，C的回文子串的左边界为centerLeftPos的外部或者边界上，也就是iiLeftPos 在centerLeftPos的右边，且iiLeftPos和centerLeftPos 有可能重合
以上三种情况就是manachar算法中的三种情况，针对三种情况右三种处理策略：
-
情况1处理：直接向外查找改位置i的最大回文半径，暴力寻找，找到之后更新下R和C（当前的最右回文右边界 和 最右回文右边界对应的回文中心）
-
情况2处理：i的回文半径就是ii点的回文半径，i和ii点的回文半径是相等的
-
情况3处理：i的回文半径就是需要从重新计算，暴力计算，但是计算可以从一个位置开始，不需要从位置向左右两边扩展，这个位置是：以C为中心，以C为中心的右回文边界开始找起
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
