Manacher（马拉车）算法学习笔记

Manacher 算法用于在 $O(n)$ 时间内寻找字符串中的最长回文子串。通过对原串进行预处理和巧妙的“镜像”思路，它将暴力中心扩展的最坏 $O(n^2)$ 降至线性。

考虑回文串的定义：

空串是回文串。
长度为 1 的串是回文串。
如果 $A$ 是回文串， $a$ 是一个字符，则 $a A a$ 是回文串。

也就是说：如果一个串是回文串，则它去掉开头和结尾的字符后亦然。这意味着一个回文子串包含着更小的回文子串。

考虑设 $\mathrm{p}_i$ 表示以 $i$ 为中心的最长回文子串长度是多少（或言： $\left[i-\operatorname{p}_i+1, i+\operatorname{p}_i-1\right]$ 是极长回文串）。

考虑回文串自带一个对称结构，维护当前所有回文串中右端点最靠右的回文串是谁，记它为（ $m, \operatorname{r}$ ）。现在枚举到一个位置 $i$ ，考虑：

当 $i>\operatorname{r}$ 的时候，直接暴力判断 $i$ 最远能向两边延申多长的回文串，然后用其更新 $r$ 。
当 $i \leq \operatorname{r}$ 的时候，说明以 $m$ 为中心， $i$ 存在一个对称点 $j=m-(i-m)$ 。容易见到 $\operatorname{len}_i \geq \min \left(\operatorname{r}-i+1, \operatorname{p}_j\right)$ ，因此可以直接取后再暴力更新。

这么做的复杂度当然是暴力更新的次数。然而每次暴力更新一定都会使得 maxr 变大，因此总复杂度线性。

例题

P3805 【模板】manacher

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 22000010;

int n, m, ans, p[N];
char s[N], t[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1), t[0] = '~';
    for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
    t[ ++ m] = '#';
    for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
        if (i <= r) p[i] = min(p[mid * 2 - i], r - i + 1);
        while (t[i - p[i]] == t[i + p[i]]) p[i] ++ ;
        if (i + p[i] > r) r = i + p[i] - 1, mid = i;
        ans = max(ans, p[i] - 1);
    }
    printf("%d\n", ans);
    return 0;
}

P4555 [国家集训队] 最长双回文串

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 400010;

int n, m, ans, p[N], L[N], R[N];
char s[N], t[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1), t[0] = '~';
    for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
    t[ ++ m] = '#';
    for (int i = 1; i <= n; i ++ ) L[i] = R[i] = 1;
    for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
        if (i <= r) p[i] = min(p[mid * 2 - i], r - i + 1);
        for (; t[i - p[i]] == t[i + p[i]]; p[i] ++ );
        if (i + p[i] > r) r = i + p[i] - 1, mid = i;
        R[i + p[i] - 1] = max(R[i + p[i] - 1], p[i] - 1);
        L[i - p[i] + 1] = max(L[i - p[i] + 1], p[i] - 1);
    }
    for (int i = m; i >= 1; i -= 2) R[i] = max(R[i], R[i + 2] - 2);
    for (int i = 1; i <= m; i += 2) L[i] = max(L[i], L[i - 2] - 2);
    for (int i = 3; i < m; i += 2) ans = max(ans, R[i] + L[i]);
    printf("%d\n", ans);
    return 0;
}

P4287 [SHOI2011] 双倍回文

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 1000010;

int n, m, p[N];
char s[N], t[N << 1];
priority_queue<PII, vector<PII>, greater<PII>> q;
set<int> st;

int main() {
    n = read();
    scanf("%s", s + 1), t[0] = '!';
    for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
    t[ ++ m] = '#';
    for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
        if (i <= r) p[i] = min(p[2 * mid - i], r - i + 1);
        for (; t[i - p[i]] == t[i + p[i]]; p[i] ++ );
        if (i + p[i] > r) r = i + p[i] - 1, mid = i;
    }
    int ans = 0;
    for (int r = 1; r <= m; r += 2) {
        q.ep(r + p[r] - 1, r), st.ep(r);
        while (q.size() && q.top().fir < r) st.erase(q.top().sec), q.pop();
        int l = r - p[r] + 1, mid = (l + r) >> 1;
        auto it = st.lower_bound(mid);
        if (it != st.end()) ans = max(ans, (r - *it) << 1);
    }
    printf("%d\n", ans);
    return 0;
}