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)