简介 Manacher(马拉车)算法，这是一个可以有极高效率的算法，常用来解决最长回文子串这一类问题Leetcode题目示例 时间复杂度可以达到O(n) 核心思想 预处理字符串： 在原始字符串中插入特殊字符（如 #）等，并且在原字符串首尾都插入特殊字符(因为不同字符显然必定不是回文子串)将奇偶长度的回文串统一处理为奇数长度。 原理 CNDS上有比我的理解更易懂清晰的讲解，附上链接原理讲解 算法步骤 1.预处理

string str = "^";//首位
        for (char c : s) {
            str += '#';
            str += c;
        }
        str += "#$";//末尾

示例 aba - #a#b#a# abba - #a#b#b#a# 2.动态规划 mid：当前已知回文串的中心位置。 r：以 mid 为中心的最右边界位置（r = mid + 半径）。 数组 dp：记录每个位置作为中心时的回文半径。 利用对称性： 了解一个公式：中点公式，众所周知，在一个数轴上，给定两个点A,B，设A,B坐标分别为~x1~,~x2~想求出线段AB的中点M，则M=(~x1~+~x2~)/2 那么同理易得，对于当前位置 i： 若 i < r，则 i 关于中心 mid 的对称点为 j = 2*mid - i。 此时dp[i]至少为 min(dp[j], r - i)（确保在已知回文范围内）。 若 i ≥ r则dp[i] = 1（无已知对称信息）。 中心扩展： 在 dp[i]的初始值基础上，向两边扩展dp[i]，同时更新mid和 r。 其实我认为就是一个类似于二分的操作，只是利用了从小学过的中点公式。

int n = str.size();
        vector<int> dp(n, 0);
        int dp = 0, right = 0;
        for (int i = 1; i < n - 1; ++i) {
            int mirror = 2 * dp - i;
            if (i < right) {
                dp[i] = min(right - i, dp[mirror]);
            }
            while (str[i + (1 + dp[i])] == str[i - (1 + dp[i])]) {
                dp[i]++;
            }
            if (i + dp[i] > right) {
                dp = i;
                right = i + dp[i];
            }
        }
        int max_len = 0;
        int dp_index = 0;
        for (int i = 1; i < n - 1; ++i) {
            if (dp[i] > max_len) {
                max_len = dp[i];
                dp_index = i;
            }
        }
        int start = (dp_index - max_len - 1) / 2;

3.最长回文子串的长度为 num[i] - 1，其起始位置可以通过 (中心点 - 半径) / 2 计算得到