Manacher 字符串算法总结

· · 算法·理论

Manacher 字符串算法总结

Manacher 算法，中文翻译俗称马拉车算法，其在字符串算法中并没有哈希和 KMP 那么有用处，不过在处理有关于回文串的问题时候则是非常快捷的线性字符串求出最大回文字串算法。

算法原理实现

Manacher 算法的题目背景是这样的，给定一个字符串 s，需要从中求出 s 的最大回文子串的长度。

很明显可以想到一个思路，我们分别对 s 做一遍哈希，然后从中枚举中间的断点，注意这里需要分情况进行讨论，比如长度为奇数或者为偶数，然后由于回文串的单调性，所以我们可以直接进行二分答案然后求取答案，时间复杂度 O(n\log n)。

但是 Manacher 算法和哈希加上二分不同，它的时间更加快速，是一个线性算法，它同样也采用了中间断点的思路，不过在进行算法流程之前还需要做一步预处理操作：在字符串的每一个相邻字符直接插上 '#' 号，以及在最后添上 '@' 和在开头添上 '^'，（其实这几个字符是什么都无所谓）。

之所以需要做预处理操作，是因为偶数和奇数的回文串不好一起考虑，需要进行分类讨论，但是经过我们的预处理，就可以只对奇数的回文串进行处理了，因为在其间添加了一些字符。

然后呢，我们需要维护一些变量来便于我们进行算法的流程，比如 R，我们定义 R 为当前上一个回文串的最大的右端点，mid 上一个回文串的回文中心点，在定义一个类似 DP 数组的 f_i 数组表示第 i 个字符作为回文中心点的最大能够扩散的回文串长度。

然后，我们每次进行处理第 i 个字符，我们来考虑，如果当前 i < R，那么如果它有回文串的长度，那么一定就会被上一个 mid 直接给覆盖，就不会在让 i 获得更高的价值；但是需要注意一点，也必须向 R - i 进行转移，因为不被覆盖的也需要覆盖在其间。

所以得出 i < R 的转移式 f_i = \min(f_{mid \times 2 - i}, r - i)。

但是如果 i > R，也就说明不是相互相交的两个回文串了，那么我们就可以直接暴力向两边进行扩展，因为并不会相交，所以最后的时间复杂度还是线性的。

模板代码：

#include <iostream>
#include <cstdio>
#include <string> 

const int N = 3e7 + 5;

std::string s, str;
int n, len, ans, r, mid, p[N];

void extend_str() {
    str = '^';
    for (int i = 0; i < s.size(); i++) {
        str += '#';
        str += s[i];
    }
    str += '#', str += '@';
    len = s.size() * 2 + 1;
}

void manacher() {
    for (int i = 1; i <= len; i++) {
        p[i] = 1;
        if (i < r) {
            p[i] = std::min(p[mid * 2 - i], r - i);
        }
        while (str[i + p[i]] == str[i - p[i]]) p[i]++;
        if (i + p[i] > r) {
            mid = i;
            r = i + p[i];
        }
        ans = std::max(ans, p[i] - 1);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> s;
    extend_str();
    manacher();
    std::cout << ans << '\n';
}