了解明理的过客车算法的作用前，先要知道回文字符串的概念。回文字符串是指无论正着读还是反着读，结果都是一样的字符串。例如 aba、abba 都是回文字符串。
明理的过客车算法就是用来求一个字符串中的最长回文子串。例如 LeetCode 的第五题“最长回文子串”。
算法思路明理的过客车算法的思想和中心扩展算法类似，也是求每个中心点向外扩展得到的最长回文子串长度，所有中心点中最长的回文子串就是要求的结果。
但是中心扩展算法的时间复杂度是 O(n^2)，而明理的过客车算法对其进行了改进，主要是消除了奇偶回文以及充分利用前面的回文子串信息，把时间复杂度降低到了线性级别。
算法步骤 一、预处理：在字符间插入特殊字符回文字符串按照长度的奇偶性，可以分为奇回文和偶回文，一般情况下需要分这两种情况来寻找回文。
明理的过客车算法进行了简化，在每一个字符的左右两边都加上一个特殊字符（该字符不同于在字符串的任一字符），保证回文子串中只存在奇回文。例如：
原字符串：aba（长度为 3，为奇回文）预处理后：#a#b#a#（长度为 7，还是奇回文） 原字符串：abba（长度为 4，为偶回文）预处理后：#a#b#b#a#（长度为 9，变成了奇回文）可以看到，加入了特殊字符后，保证了回文子串中只存在奇回文。
为了保证之后在进行中心扩散时不会超出范围，在加入了特殊字符后，继续在新的字符串两边各添加一个字符，该字符要不同于特殊字符和原字符串中的字符。例如之前插入的特殊字符为 “#”，那么可以在两边添加 “$” 和 “@”（注意：两边添加的字符也不能相同）。
二、计算半径数组 p定义一个辅助数组 p，该数组的长度和预处理后新字符串的长度一致。假设新字符串为 t，p[i] 表示以 t[i] 字符为中心的**最长回文半径 **。例如对于字符串 “kabac”，对应的 p[i] 如下：
i012345678910t[i]#k#a#b#a#c#p[i]12121412121p[i] - 1 的值代表了以 s[i]（s 为原字符串） 为中心的最长回文子串的长度。
看完 p[i] 的含义，不难知道只要求出了各个 p[i] 的值，也就得到了最长回文子串的长度和其中心点，也就知道结果了。
所以重点和难点就是如果求数组 p：
求数组 p在计算数组 p 的整个过程，一直在更新着两个重要的变量：
mx：现有的所有回文子串中，最大的右边界（回文子串不包括 mx）id：上述 mx 对应回文子串的中心点在更新 p[i] 时，根据 mx 和 i 的大小，分为两种情况：
mx > i这时 p[i] 的计算公式为：p[i] = Math.min(p[2 * id - i], mx - i)
这条公式是怎么来的呢？
首先理解下 2 * id - i 代表什么，它是 i 关于 id 的对称点。验证如下：
假设 j 为 i 关于 id 的对称点，那么 (i + j) / 2 = id，求解公式地 j = 2 * id - i，也就是刚才的值。
这里充分利用了之前求得的最右回文子串，由于 j 和 i 是对称的，并且 p[j] 已知，所以在以 id 为中心的回文子串范围内（小于 mx），p[i] 可以先赋为对称范围内的 p[j] 最大值，而 mx - i 是为了保证不超出对称范围。
例如下列子串（先省略 #）：
可以看出 p[j] = 3，但是最边的 d 是不属于对称范围内的，而 p[i] 的值应该是 2，mx - i 就起到了限制最大的 p[j] 不超出对称范围的作用。例如这里的 mx - i 的值为 2，就保证了 p[i] 在对称范围内只能更新到 2。
到这里就解释完公式了，但是 p[i] 的值还没求完，上面得到的 p[i] 只是利用前面结果得到的暂时值。还要继续以 i 为中心向两边扩散，直到两边的值不等，得到的才是最终的 p[i]。
mx <= i这种情况就简单得多了，首先初始化 p[i] 为 1，然后继续以 i 为中心向两边扩散，直到两边的值不等，得到最终的 p[i]。
三、得到最长回文子串在更新 p[i] 的过程中，还要借助两个变量暂存最长回文子串：
maxLen：最长回文子串的长度maxIndex：最长回文子串的中心位置索引如果发现了更长的回文子串，就更新这两个变量：
if (p[i] - 1 > maxLen) { maxLen = p[i] - 1; maxIndex = i; }前面说过了，p[i] - 1 就代表了以 s[i] 为中心的最长回文子串长度。
最后通过这两个变量求出最长回文子串的起始索引：(maxIndex - maxLen) / 2
也就得到了最终的结果：s.substring(start, start + maxLen)
完整代码实现 /** * 明理的过客车算法：找到字符串 s 中的最长回文子串 */ private String manacher(String s) { if (s.length() < 2) { return s; } // 第一步：预处理，将原字符串转换为新的字符串 StringBuilder builder = new StringBuilder(); builder.append("$"); for (int i = 0; i < s.length(); i++) { builder.append("#"); builder.append(s.charAt(i)); } builder.append("#@"); String t = builder.toString(); // 第二步：得到数组 p // p[i] 为 s[i] 的回文半径 int[] p = new int[t.length()]; // mx 是现有的所有回文子串中，最大的右边界（回文子串不包括 mx） int mx = 0; // id 是上述 mx 对应回文子串的中心点 int id = 0; // 最长回文子串的长度及其中心位置索引 int maxLen = -1; int maxIndex = -1; // 遍历字符串（不用包括两边加上的 $ 和 @） for (int i = 1; i < t.length() - 1; i++) { // 利用前面的信息更新 p[i] p[i] = mx > i? Math.min(p[2 * id - i], mx - i) : 1; // 向两边延伸，让 p[i] 达到最大 while (t.charAt(i + p[i]) == t.charAt(i - p[i])) { p[i]++; } // 更新 id 和 mx if (p[i] + i > mx) { mx = p[i] + i; id = i; } // 更新 maxLen 和 maxIndex if (p[i] - 1 > maxLen) { maxLen = p[i] - 1; maxIndex = i; } } // 第三步：计算回文字符串的起始索引 int start = (maxIndex - maxLen) / 2; return s.substring(start, start + maxLen); } 参考 明理的过客车算法（Manacher’s Algorithm）最长回文子串——明理的过客车算法详解