Wiki › Thuật toán › Thuật toán xâu › Manacher

Manacher

huunguyen Updated Tháng sáu 2, 2026

Thuật toán Manacher tính bán kính palindrome lớn nhất tại mọi tâm của một xâu trong $O (N)$ , từ đó giải hàng loạt bài liên quan đến chuỗi con đối xứng: tìm palindrome dài nhất, đếm số chuỗi con palindrome, kiểm tra một đoạn có đối xứng không... Cách ngây thơ (brute force) duyệt mỗi tâm rồi mở rộng mất $O (N^{2})$ ; với $N$ lên tới $10^{6}$ thì chỉ Manacher với $O (N)$ mới chạy kịp.

Ý tưởng / Trực giác

Định nghĩa $p [i]$ là bán kính palindrome lớn nhất có tâm tại $i$ , tức là đoạn $s [i - p [i] . . i + p [i]]$ là palindrome. Cách brute force tính lại $p [i]$ từ con số $0$ cho mỗi $i$ là lãng phí, vì các palindrome chồng lấn nhau rất nhiều.

Mấu chốt là tính đối xứng. Giả sử trong lúc duyệt ta đang giữ palindrome "phủ xa nhất về bên phải", gọi là $[l, r]$ với tâm $c$ (nên $l = 2 c - r$ ). Xét một tâm $i$ nằm bên trong đoạn này ( $i < r$ ). Gọi $i^{'} = 2 c - i$ là vị trí đối xứng của $i$ qua $c$ . Vì cả đoạn $[l, r]$ đối xứng quanh $c$ , nên cấu trúc xâu quanh $i$ và quanh $i^{'}$ là như nhau chừng nào còn nằm trong $[l, r]$ . Do đó ta suy ra ngay:

$p [i] \geq min (p [i^{'}], r - i) .$

Nếu palindrome tại $i^{'}$ nằm gọn trong $[l, r]$ (tức $p [i^{'}] < r - i$ ) thì $p [i] = p [i^{'}]$ chính xác, không cần so sánh ký tự nào.
Nếu nó chạm hoặc vượt biên $r$ (tức $p [i^{'}] \geq r - i$ ), ta chỉ chắc chắn được tới biên ( $p [i] \geq r - i$ ), phần ngoài $[l, r]$ chưa biết gì nên phải mở rộng thủ công từng ký tự.

Nhờ vậy, mỗi lần "mở rộng thủ công" đều đẩy biên phải $r$ tiến lên. Vì $r$ chỉ tăng, không lùi, tổng số lần so sánh ký tự qua toàn bộ vòng lặp bị chặn bởi $O (N)$ — đây là lý do thuật toán đạt tuyến tính.

Xử lý palindrome chẵn và lẻ cùng lúc

Palindrome độ dài lẻ có tâm là một ký tự, palindrome độ dài chẵn có tâm nằm "giữa hai ký tự". Để khỏi viết hai trường hợp, ta chèn ký tự ngăn cách # vào giữa mọi ký tự và ở hai đầu:

s    = a b a a b
t    = # a # b # a # a # b #

Xâu $t$ luôn có độ dài lẻ ( $2 N + 1$ ), nên mọi palindrome (cả chẵn lẫn lẻ của $s$ ) đều trở thành palindrome độ dài lẻ trong $t$ , có tâm là một vị trí cụ thể. Một tính chất đẹp: với mọi $i$ , $p [i]$ trong xâu $t$ đúng bằng độ dài palindrome tương ứng trong xâu gốc $s$ . Ví dụ tâm tại một dấu # cho palindrome chẵn, tâm tại một chữ cái cho palindrome lẻ.

Ví dụ chạy tay

Xét $s =$ abaab. Xâu biến đổi và kết quả $p []$ :

 t   :  #  a  #  b  #  a  #  a  #  b  #
 idx :  0  1  2  3  4  5  6  7  8  9 10
 p   :  0  1  0  3  0  1  4  1  0  1  0

Theo dõi vài bước với cặp $(c, r)$ là tâm/biên phải của palindrome phủ xa nhất:

i=1 (t[1]='a'): i>=r → mở rộng thủ công.
   so #a# : t[0]==t[2] ('#'=='#') ✓ → p[1]=1.
   biên mới: c=1, r=2.

       #  a  #
       l  c  r
       0  1  2     p[1]=1  (palindrome "a")

i=3 (t[3]='b'): i>=r → mở rộng.
   #b#, ##(a#a)## ... so tới khi t[3-3]=t[0]='#', t[3+3]=t[6]='#' ✓ → p[3]=3.
   biên mới: c=3, r=6.

    #  a  #  b  #  a  #
    l        c        r
    0developing 1  2  3  4  5  6     p[3]=3  (palindrome "aba")

i=5 (t[5]='a'): i<r (5<6). i'=2c-i=2*3-5=1, p[1]=1, r-i=6-5=1.
   p[5] >= min(1,1)=1, sau đó thử mở rộng: t[5-2]=t[3]='b' vs t[5+2]=t[7]='a' ✗.
   → p[5]=1, biên không đổi.

i=6 (t[6]='#'): i>=r → mở rộng.
   so dần: a#a, #(a#a)#, b#(...)#b, ... tới t[2]='#',t[10]='#' ✓ → p[6]=4.
   biên mới: c=6, r=10.

 #  a  #  b  #  a  #  a  #  b  #
 l                 c              r
 0  1  2  3  4  5  6  7  8  9 10     p[6]=4  (palindrome "baab")

Giá trị lớn nhất là $p [6] = 4$ , ứng với palindrome dài nhất baab (độ dài $4$ ). Lưu ý ở $i = 5$ , vì $i$ nằm trong $[l, r]$ nên ta khởi tạo ngay từ giá trị đối xứng thay vì bắt đầu từ $0$ — đó chính là chỗ tiết kiệm.

Cài đặt

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

// Trả về mảng p[] trên xâu ĐÃ biến đổi t = #s[0]#s[1]#...#
// p[i] = bán kính palindrome tại i = ĐỘ DÀI palindrome tương ứng trong s.
vector<int> manacher(const string& s) {
    // Bước 1: chèn '#' để gộp palindrome chẵn/lẻ
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();

    vector<int> p(n, 0);
    int c = 0, r = 0;   // palindrome phủ xa nhất hiện tại: [c-r? ] tâm c, biên phải r

    for (int i = 0; i < n; i++) {
        // Bước 2: tận dụng đối xứng nếu i nằm trong [.., r)
        if (i < r) {
            int mirror = 2 * c - i;            // vị trí đối xứng của i qua c
            p[i] = min(r - i, p[mirror]);      // chặn trên bởi biên r
        }
        // Bước 3: mở rộng thủ công phần chưa chắc chắn
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1])
            p[i]++;
        // Bước 4: nếu vượt biên phải, cập nhật tâm/biên phủ xa nhất
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
    }
    return p;
}

int main() {
    string s; 
    cin >> s;
    auto p = manacher(s);
    int ans = 0;
    for (int x : p) ans = max(ans, x);   // độ dài palindrome dài nhất
    cout << ans << "\n";
    return 0;
}

Các ứng dụng từ mảng $p []$

1. Độ dài palindrome dài nhất: chính là ${max}_{i} p [i]$ (vì $p [i]$ trên $t$ bằng đúng độ dài trên $s$ ).

2. Kiểm tra đoạn $s [l . . r]$ (0-based) có phải palindrome không. Tâm của đoạn này trong xâu $t$ nằm tại vị trí $l + r + 1$ (mỗi ký tự gốc chiếm 2 vị trí trong $t$ ). Đoạn là palindrome khi và chỉ khi bán kính tại tâm đủ phủ hết:

// p[l + r + 1] >= r - l + 1  ⟺  s[l..r] là palindrome
bool isPalin(const vector<int>& p, int l, int r) {
    return p[l + r + 1] >= r - l + 1;
}

3. Đếm tổng số chuỗi con là palindrome: $\sum_{i} ⌈ \frac{p [i]}{2} ⌉$ (trên xâu $t$ ). Mỗi tâm đóng góp số palindrome bằng nửa bán kính làm tròn lên.

Độ phức tạp

Thời gian: $O (N)$ . Vòng for chạy $2 N + 1$ lần. Mỗi bước trong while (mở rộng thủ công) đều làm biên phải $r$ tăng ít nhất $1$ ; vì $r$ chỉ tăng trong suốt thuật toán và bị chặn bởi $n = 2 N + 1$ , tổng số lần lặp while qua toàn bộ vòng for là $O (N)$ . Các thao tác còn lại trong mỗi vòng là hằng số.
Bộ nhớ: $O (N)$ . Cần xâu biến đổi $t$ độ dài $2 N + 1$ và mảng $p []$ cùng kích thước. Không dùng thêm cấu trúc phụ.

⚠️ Lỗi thường gặp

Quên kẹp $p [i]$ bởi $r - i$ . Nếu chỉ gán p[i] = p[mirror] mà không lấy min(r - i, p[mirror]), khi palindrome đối xứng vượt biên $r$ ta sẽ "copy" một bán kính lớn hơn thực tế cho phần ngoài $[l, r]$ (phần đó chưa được kiểm chứng) → kết quả sai. Luôn chặn trên bằng r - i.
Nhầm điều kiện cập nhật biên. Phải cập nhật khi i + p[i] > r (so biên phải mới với biên phải cũ), không phải p[i] > r hay i + p[i] > c. Cập nhật sai khiến cửa sổ $[l, r]$ không còn là palindrome phủ xa nhất, phá vỡ bất biến của thuật toán.
Sai biên trong while, gây truy cập ngoài mảng. Phải kiểm tra cả i - p[i] - 1 >= 0 lẫn i + p[i] + 1 < n TRƯỚC khi so sánh t[...]. Quên một vế sẽ đọc ngoài mảng (undefined behavior) hoặc thiếu/thừa một bước mở rộng. Dùng ký tự # ở hai đầu cũng giúp vòng lặp tự dừng ở biên.
Quên rằng $p [i]$ trên $t$ là độ dài trên $s$ , không phải bán kính trên $s$ . Đây là điểm dễ nhầm nhất: nhiều người chia đôi $p [i]$ một cách không cần thiết. Trên xâu biến đổi, $p [i]$ đã đúng bằng độ dài palindrome gốc — in trực tiếp max(p[i]).
Off-by-one khi quy đổi tâm để kiểm tra đoạn $[l, r]$ . Công thức tâm là $l + r + 1$ (với chỉ số 0-based của $s$ ). Lệch $1$ do quên ký tự # ở đầu là lỗi kinh điển khi làm phần truy vấn palindrome.
Đọc xâu sai khi có khoảng trắng hoặc xâu rỗng. cin >> s dừng ở khoảng trắng; nếu đề cho phép khoảng trắng phải dùng getline. Với xâu rỗng, $t =$ "#" và $max p = 0$ — hãy đảm bảo phần in kết quả xử lý đúng trường hợp này.

Biến thể / Mở rộng

Truy vấn palindrome cho đoạn tĩnh: kết hợp mảng $p []$ với công thức tâm $l + r + 1$ để trả lời mỗi truy vấn trong $O (1)$ .
Khi xâu có cập nhật (thay ký tự): Manacher tĩnh không còn dùng được; chuyển sang hashing hai chiều (so prefix-hash xuôi với prefix-hash ngược) cộng cây Fenwick/segment tree để kiểm tra palindrome đoạn sau cập nhật.
Đếm số palindrome phân biệt: vượt quá Manacher; cần cây palindrome (Eertree / palindromic tree).

Bài tập luyện

Palindrome Dài Nhất (longpalin) — (Nâng cao) Tìm và in ra chuỗi con palindrome dài nhất với $N \leq 10^{6}$ — bài "kinh điển" áp dụng trực tiếp Manacher, buộc dùng $O (N)$ vì $O (N^{2})$ sẽ TLE.
Palindrome Dài Nhất tại mỗi vị trí (allpalin) — (Nâng cao) Với mỗi vị trí, tính độ dài palindrome dài nhất kết thúc tại đó; cần khai thác đầy đủ mảng $p []$ (mỗi tâm phủ một khoảng vị trí kết thúc) chứ không chỉ lấy max.
Truy Vấn Palindrome (palinq) — (Kỳ cựu) Kiểm tra một đoạn con có là palindrome không, xen kẽ thao tác cập nhật ký tự; minh hoạ ranh giới của Manacher tĩnh và động lực chuyển sang hashing + cấu trúc dữ liệu cho phiên bản có cập nhật.