理解Manacher算法的重要步骤

1，暴力方法如何寻找最长回文子串 2，Manacher扩展串，可以方便的寻找奇长度、偶长度的回文，扩展字符可以随意设置，不会影响计算3，回文半径和真实回文长度的对应，真实长度=p[i]-1 4、扩展回文串结尾下标和真实回文串终止位置的对应，真实回文串终止位置 = 扩展回文串结尾下标 /2 5、理解回文半径数组p、理解回文覆盖最右边界r、理解回文中心c，课上会图解 6、Manacher算法的加速过程，当来到的中心点i，如何利用p、r、c来进行回文扩展，课上详细图解

a，i没有被r包住，那么以i为中心直接扩展 b，i被r包住，对称点2*c-i 的回文半径， 在大回文区域以内，直接确定p[i]=p[2*c-i] C，i被r包住，对称点 2*c-i 的回文半径,在大回文区域以外，直接确定p[i]=r-i d，i被r包住，对称点2*c-i 的回文半径，撞线大回文区域的边界，从r之外的位置进行扩展

7、Manacher算法的时间复杂度分析，时间复杂度O(n) 8、Manacher算法代码讲解，理解巧妙的while是如何兼顾四种情况的，代码中无需四种情况的判断

https://www.bilibili.com/video/BV1YH4y1h7MU/?spm_id_from=333.337.search-card.all.click&vd_source=516557f2525ba2ce9681cb21259ba063

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int manacher(const string& str) {
    if (str.empty()) return 0;

    // 将原始字符串处理成带分隔符的形式（如：abc -> #a#b#c#）
    string ss;
    for (char c : str) {
        ss += "#";
        ss += c;
    }
    ss += "#";

    int n = ss.size();
    vector<int> p(n, 0); // 回文半径数组
    int maxLen = 0;      // 最大回文半径
    int c = 0, r = 0;    // 当前回文中心 c 和右边界 r

    for (int i = 0; i < n; i++) {
        // 初始化当前点的回文半径
        int len = (i < r) ? min(p[2 * c - i], r - i) : 1;

        // 尝试扩展回文半径
        while (i - len >= 0 && i + len < n && ss[i - len] == ss[i + len]) {
            len++;
        }

        // 更新回文半径数组
        p[i] = len;

        // 如果当前回文右边界超过了 r，则更新 c 和 r
        if (i + len > r) {
            c = i;
            r = i + len;
        }

        // 更新最大回文半径
        maxLen = max(maxLen, len);
    }

    // 返回最长回文子串的长度（去掉分隔符的影响）
    return maxLen - 1;
}

int main() {
    string str;
    cout << "请输入字符串: ";
    cin >> str;

    int result = manacher(str);
    cout << "最长回文子串的长度是: " << result << endl;

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com