Manacher算法

马拉车算法

最长回文子串的朴素解法

回文串：如果一个长度为n的字符串s为回文串，n可为奇数或偶数，对应两种情况：

n为奇数时，回文中心为C, 回文半径为R：
$\forall i \in [0, R), \, s[C-i] = s[C+i], \, 2R+1=n$

n为偶数时，回文中心为$C_1, C_2$，回文半径为R：
$\forall i \in [0, R), \, s[C_1-i] = s[C_2+i], \, 2R=n$

string preProcess(const string& s) {
    string ret = "^";
    for (auto ch: s) {
        ret += '#';
        ret += ch;
    }
    ret += "#$";
    return ret;
}
string longestPalindrome(string s) {
    string sx = preProcess(s);
    int n = sx.size();
    vector<int> P(n);
    int C = 0, R = 0;
    for (int i = 1; i < n-1; ++i) {
        int mirror_i = 2 * C - i;
        if (R > i) P[i] = min(P[mirror_i], R - i);
        while (sx[i-P[i]-1] == sx[i+P[i]+1]) ++P[i];
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }
    int max_len = 0, max_id = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (P[i] > max_len) {
            max_len = P[i];
            max_id = i;
        }
    }
    int st = (max_id - max_len) >> 1;
    return s.substr(st, max_len);
}