题解 | #最长回文子串#

#include <utility>
#include <vector>
class Solution {
  public:
    string preprocess(const string& s) { //预处理字符串
        string result = "^#"; //‘^’为开始标识符
        for (char c : s) {
            result += c;
            result += "#"; //间隔插入‘#’号，将奇数和偶数长度的回文串统一为奇数长度
        }
        result += "$"; //‘$’为结束标识符，开始和结束标识符用于防止访问越界
        return result;
    }
    int getLongestPalindrome(string A) {
        A = preprocess(A); //预处理字符串
        int n = A.size();
        vector<int> P(n, 1); //P[i]表示以A[i]为中心的回文串的半径（含中心）
        int id = 0, mx = 0, maxLen = 0; //id表示已知右边界最右的回文串的中心位置，mx表示该回文串的右边界（即目前的最右边界），maxlen用于记录处理后字符串的最长回文串的长度
        for (int i = 1; i < n - 1; ++i) {
            int i_mirror = 2 * id - i; //i_mirror表示i关于id的对称点（id-(i-id)）
            if (mx > i) P[i] = min(mx - i, P[i_mirror]); // 点睛之笔！根据回文串的对称性，已知右边界最右的回文串的左右两部分内的对称点应具有在该回文串直径范围内相同的回文半径，若超出该回文串范围，则只截取到右边界。
            while (A[i + P[i]] == A[i - P[i]]) { //中心扩散法确定i位置的回文半径，即使mx>i也要经过这一步的检查
                P[i]++;
            }
            if (P[i] + i > mx) { //若新的回文串右边界超出mx，则更新中心点id和最右边界mx
                id = i;
                mx = P[i] + i;
            }

            maxLen = P[i] > maxLen ? P[i] : maxLen; //更新最长长度
        }
        return maxLen - 1;  //(x+x+1)/2 +0.5=maxlen => x=maxlen-1，x是要求的原始最大长度，+0.5是因为插入‘#’后必为奇数长度，求包含中心的半径长度要在除2后加0.5
    }
};