(资料图片仅供参考)

马拉车的定义

马拉车本质是对中心扩展法（暴力算法）的优化。

马拉车是干什么的

Manacher算法帮助我们在给定的字符串中找到最长的回文子串。为了简单起见，我们先只处理有奇数个字符的字符串，关于偶数个字符的字符串，在文章最后会给出解法。我们的处理思路和暴力算法基本一致，那就是从左到右一个字符一个字符来处理这个字符串，寻找以当前处理的字符为中心的最长回文串，假设字符串的长度是N，那我们就在寻找到的N个最长回文串中取最长的就是答案了。

符号说明

我们约定，c是我们处理当前字符时，已经找到的右边界最大的回文字符串的中心。l和r分别是这个最长的回文字符串的左界和右界，也就是最左边的字符索引和最右边的字符索引。现在，我们举个例子来理解c、l和r。例子：“abacabacabb”当从左到右一个字符一个字符计算时，我们用i表示当前正在处理的字符的索引，当i在索引1时，最长的回文字符串是 "aba"（长度=3）。当i在索引5时，如下图所示：最长的回文字符串的答案是9，c、l、r的值如图中所示。不难看出，c所代表的最长回文字符串现在我们知道了c、l和r表示什么，为了下面算法的讲解更加自然，我们需要了解一个概念：镜像索引。对于以c为中心的任何一个回文字符串来说 索引j关于c的镜像是j"，如下图所示：观察上图，不难得出下面的计算公式：

c - j = j" - c

此时，j的镜像j":

j" = (2 * c) - j

模板

#include #include #include #include using namespace std;const int maxn = 3e5 + 5;char s[maxn], t[maxn];int p[maxn];int main() {    while (~scanf("%s", s)) {        int l = strlen(s), len = 0;        t[len++] = "$"; // 在字符串开头和结尾都添加一个特殊字符(如"$",                        // 注意不要相同)，使后续计算可以避免判断越界        t[len++] = "#";        for (int i = 0; i < l; ++i) {            t[len++] = s[i];            t[len++] = "#";        }        t[len] = "&";        int center = 0, max_right = 0;        for (int i = 1; i < len; ++i) {            int i_mirror = 2 * center - i;            if (max_right >                i) { // 在最右边界的覆盖范围内, 就利用回文串特征计算长度                p[i] = min(max_right - i,                           p[i_mirror]); // 使用min()是为了防止超出最右边界            } else {                p[i] = 0;            }            while (t[i - 1 - p[i]] == t[i + 1 + p[i]])                ++p[i];            if (i + p[i] > max_right) { // 更新右边界的回文串中心                center = i;                max_right = i + p[i];            }        }        int max_len = 0;        // int pos = 0;  //记录最长回文子串中心的位置        for (int i = 1; i < len; ++i)            if (max_len < p[i]) {                max_len = p[i];                // pos = i;            }        printf("%d\n", max_len); //最长回文串的起始位置为: (pos - max_len) / 2    }    return 0;}

关键词：