题解 | #【模板】马拉车算法#

题目链接

【模板】马拉车算法

题目描述

给定一个仅由小写字母组成的字符串 $s$ ，长度为 $n$ 。请计算 $s$ 的最长回文子串的长度。

解题思路

马拉车（Manacher）算法：在线性时间 $\mathcal{O}(n)$ 求最长回文子串。
预处理：将原串插入分隔符，形如： $t = ^\#s_1\#s_2\#\cdots\#s_n\#$,$ 再在两端加上哨兵（如 ^ 与 $），统一奇偶长度回文的处理。设新串长度为 $m$ 。
核心变量：
- $\text{center}$ ：当前已知回文最长右边界对应的中心；
- $\text{right}$ ：该回文的最右端位置；
- $P[i]$ ：以位置 $i$ 为中心的“回文半径”（包含分隔符的半径）。
线性扩展：对每个 $i$ ，若 $i<\text{right}$ ，可先取 $P[i]=\min\big(P[2\cdot\text{center}-i],\ \text{right}-i\big)$ 作为初值，再向两侧继续匹配扩展。若超出，则更新 $(\text{center},\text{right})$ 。
答案换算：最终结果为 $\max P[i]-1$ （减去分隔符的影响）。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; if (!(cin >> s)) return 0;
    // 预处理：^#s0#s1#...#sn#$
    string t; t.reserve(s.size() * 2 + 3);
    t.push_back('^');
    t.push_back('#');
    for (char c : s) { t.push_back(c); t.push_back('#'); }
    t.push_back('$');

    int m = (int)t.size();
    vector<int> P(m, 0);
    int center = 0, right = 0;
    for (int i = 1; i < m - 1; ++i) {
        int mirror = 2 * center - i;
        if (i < right) P[i] = min(P[mirror], right - i);
        while (t[i + 1 + P[i]] == t[i - 1 - P[i]]) ++P[i];
        if (i + P[i] > right) { center = i; right = i + P[i]; }
    }
    int ans = 0;
    for (int i = 1; i < m - 1; ++i) ans = max(ans, P[i] - 1);
    cout << ans + 1  << '\n';
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder t = new StringBuilder();
        t.append('^').append('#');
        for (int i = 0; i < s.length(); i++) { t.append(s.charAt(i)).append('#'); }
        t.append('$');
        int m = t.length();
        int[] P = new int[m];
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; i++) {
            int mirror = 2 * center - i;
            if (i < right) P[i] = Math.min(P[mirror], right - i);
            while (t.charAt(i + 1 + P[i]) == t.charAt(i - 1 - P[i])) P[i]++;
            if (i + P[i] > right) { center = i; right = i + P[i]; }
        }
        int ans = 0;
        for (int i = 1; i < m - 1; i++) ans = Math.max(ans, P[i] - 1);
        System.out.println(ans + 1);
    }
}

s = input().strip()

# 预处理：^#s0#s1#...#sn#$
t = ['^', '#']
for ch in s:
    t.append(ch)
    t.append('#')
t.append('$')

m = len(t)
P = [0] * m
center = 0
right = 0
for i in range(1, m - 1):
    mirror = 2 * center - i
    if i < right:
        P[i] = min(P[mirror], right - i)
    while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
        P[i] += 1
    if i + P[i] > right:
        center = i
        right = i + P[i]

ans = 0
for i in range(1, m - 1):
    if P[i] - 1 > ans:
        ans = P[i] - 1
print(ans + 1)

算法及复杂度

算法：马拉车算法；分隔符与哨兵统一奇偶长度回文，中心扩展并维护最右覆盖。
时间复杂度： $\mathcal{O}(n)$ 。
空间复杂度： $\mathcal{O}(n)$ 。