Manacher

sccc_ · 2025-07-29 16:46:55 · 个人记录

定义

Manacher，它可以在 O(n) 的时间复杂度下，求出一个串的最长回文子串长度或所有回文串个数。

实现步骤

初始化

选择一个中心，向两边扩展，但如果字符串长度为偶数，就不好处理了。

此时，我们可以将字符串里两两字符中间都插入一个同样的字符，字符串开头的左边与结尾的右边也插一个与上面同样的字符，他就可以变成奇数长度的字符串，长度为 2 \times (|s| - 1) + 1。

void add() {
    str += '^';
    int len = s.size() - 1;
    for (int i = 0; i <= len; i++) {
        str += '#';
        str += s[i];
    }
    str += "#@";
    m = 2 * len + 1;
    return;
}

核心部分

定义 p_i 为当中心为 i 时的最长回文半径，R 为最右回文边界 + 1，mid 为 $R 代表的字符串的回文中心。

定义字符串 s = "ababa"，则初始化后新字符串 str = "#a#b#a#b#a#"，则 p 为：

注意，初始时，p_i 为 1，因为自己也算回文子串。

接着我们发现，p 貌似也形成了一个回文数组。所以，我们可以得出以下结论：

• 当 i < R 时，我们在访问 i 时，我们可以直接取 p_{2 \times mid - i} 的答案，但是，如果 i + p_i > R，答案只能取 R - i。所以，结果应该是 \min(p_{2 \times mid - i}, R - i)。

• 当 i \ge R 时，p_i 只能等于 1。

p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);。

接着，p_i 要向外扩散，以获取最优答案。

即 str_{i + p_i} = str_{i-p_i} 时，p_i 可以加一（向外扩散一步）。

while (str[i + p[i]] == str[i - p[i]]) {
    p[i]++;
}

最后，当 i 变得比 R 更优（更大）时，我们需要更新 R 与 mid。

if (i + p[i] > R) {
    R = i + p[i], mid = i;
}

若题目要求求最长回文子串长度，因为我们之前加了字符，所以其实最长回文子串长度就是 p_i - 1。

即 ans = max(ans, p[i] - 1);。

P3805 【模板】manacher

#include <bits/stdc++.h>

using namespace std;

const int N = 3e7 + 10;

string s, str;
int n, m, p[N];

void add() {
    str += '^';
    int len = s.size() - 1;
    for (int i = 0; i <= len; i++) {
        str += '#';
        str += s[i];
    }
    str += "#@";
    m = 2 * len + 1;
    return;
}

void manacher() {
    int R = 0, mid = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);
        while (str[i + p[i]] == str[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > R) {
            R = i + p[i], mid = i;
        }
        ans = max(ans, p[i] - 1);
    }
    cout << ans;
} 

signed main() {
    cin >> s;
    add(), manacher();
    return 0;
} 

P3501 [POI 2010] ANT-Antisymmetry

向外扩展的条件是：一个 0 一个 1。我们可以直接异或，特判双为字符情况即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e6 + 10;

string s, str;
int n, m, p[N];

void add() {
    str += '^';
    for (int i = 0; i < n; i++) {
        str += '#';
        str += s[i];
    }
    str += "#@";
    m = 2 * n + 1;
    return;
}

bool check(char x, char y) {
    return (((x - '0') ^ (y - '0')) == 1) || (x == '#' && y == '#');
}

void manacher() {
    int R = 0, mid = 0, ans = 0;
    for (int i = 1; i <= m; i += 2) {
        p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);
        while (check(str[i - p[i]], str[i + p[i]])) {
            p[i]++;
        }
        if (i + p[i] > R) {
            R = i + p[i], mid = i;
        }
        ans += (p[i] - 1) / 2;
    }
    cout << ans;
    return;
} 

signed main() {
    cin >> n >> s;
    add(), manacher();
    return 0;
}