Skip to content

Bài 20: Manacher - Tìm Palindrome Dài Nhất

Tác giả: FPTOJ Team
Nội dung tham khảo từ: VNOI Wiki - Thuật toán Manacher

Bản chất vấn đề

Cho xâu \(S\) độ dài \(N\), tìm palindrome con liên tiếp dài nhất.

Palindrome là xâu đọc xuôi ngược đều giống nhau, ví dụ aba, abba, racecar.

Palindrome có hai loại:

Loại Ví dụ Tâm
Lẻ aba Ký tự b ở giữa
Chẵn abba Khoảng giữa hai ký tự b

Nếu xử lý riêng hai loại, code sẽ phức tạp và dễ sai. Manacher giải quyết bài toán này trong \(O(N)\) bằng cách chuyển tất cả thành palindrome lẻ.

So sánh các phương pháp:

Phương pháp Độ phức tạp Ghi chú
Duyệt cặp \((i,j)\), kiểm tra palindrome \(O(N^3)\) Quá chậm
Hash xâu + Binary Search \(O(N \log N)\) Khá tốt
Manacher \(O(N)\) Tuyến tính, tốt nhất

Tư duy cốt lõi

Bước 1: Chèn ký tự đặc biệt

Chèn ký tự # giữa mỗi ký tự, thêm ^ ở đầu và $ ở cuối để tránh kiểm tra biên.

Xâu \(S\) = abba trở thành \(T\) = ^#a#b#b#a#$.

Sau khi chèn, mọi palindrome đều có độ dài lẻ. Bán kính palindrome tại vị trí \(i\) trong \(T\) chính là độ dài palindrome gốc trong \(S\).

Xâu gốc Xâu đã chèn \(T\) Bán kính
aba (3 ký tự) #a#b#a# 3
abba (4 ký tự) #a#b#b#a# 4

Công thức: palindrome dài \(L\) trong \(S\) có bán kính \(L\) trong \(T\).

Bước 2: Mảng \(P\) và kỹ thuật nhân đôi thông tin

Định nghĩa \(P[i]\) = bán kính palindrome lớn nhất có tâm tại \(i\) trong \(T\).

Ví dụ với \(T\) = ^#a#b#b#a#$:

Chỉ số \(i\) 0 1 2 3 4 5 6 7 8 9 10
\(T[i]\) ^ # a # b # b # a # $
\(P[i]\) 0 0 1 0 1 4 1 0 1 0 0

\(P[5]=4\) nghĩa là palindrome dài nhất có tâm tại index 5 có bán kính 4, tức là abba dài 4 ký tự trong xâu gốc.

Bước 3: Tận dụng thông tin đã tính

Khi tính \(P[i]\), giả sử ta đã biết palindrome bao quanh tâm \(C\) với biên phải \(R\). Gọi \(i_{mirror} = 2C - i\) là điểm đối xứng của \(i\) qua \(C\).

Nếu \(P[i_{mirror}]\) đã biết, ta có thể khởi tạo \(P[i]\) mà không cần so sánh lại từ đầu. Có ba trường hợp:

Trường hợp Điều kiện Kết luận
1 \(i \geq R\) Không có thông tin reuse, \(P[i]=0\), mở rộng từ đầu
2 \(i < R\) và \(P[i_{mirror}] < R - i\) Palindrome tại \(i_{mirror}\) nằm trong palindrome tại \(C\), nên \(P[i] = P[i_{mirror}]\)
3 \(i < R\) và \(P[i_{mirror}] \geq R - i\) Palindrome tại \(i_{mirror}\) tràn ra ngoài, \(P[i] \geq R-i\), cần mở rộng thêm

Sau khi tính xong \(P[i]\), nếu \(i + P[i] > R\) thì cập nhật \(C = i\), \(R = i + P[i]\).

Phân tích tính đúng đắn

Tại sao kỹ thuật nhân đôi thông tin đúng?

Palindrome đối xứng qua tâm \(C\), nên mọi vị trí \(i\) nằm trong palindrome tâm \(C\) đều có "bản sao" tại \(i_{mirror} = 2C - i\).

Trường hợp 2: \(P[i_{mirror}] < R - i\) nghĩa là toàn bộ palindrome tại \(i_{mirror}\) nằm trong phạm vi \([C-(R-C), R]\). Do đối xứng, palindrome tại \(i\) có ít nhất cùng bán kính, và không thể lớn hơn vì ký tự ngay bên ngoài biên đã khác.

Trường hợp 3: \(P[i_{mirror}] \geq R - i\) nghĩa là palindrome tại \(i_{mirror}\) chạm hoặc vượt biên phải \(R\). Do đối xứng, palindrome tại \(i\) có ít nhất bán kính \(R-i\). Phần vượt ra ngoài chưa được kiểm tra, nên cần mở rộng thêm.

Tại sao duyệt từ trái sang phải đảm bảo đúng?

Khi duyệt \(i\) từ 1 đến \(n-2\), mỗi vị trí chỉ cập nhật \(C\) và \(R\) khi mở rộng ra ngoài. Biên phải \(R\) chỉ tăng, không giảm. Mọi \(i < R\) đều có thể reuse thông tin từ \(i_{mirror} < i\) (vì \(i_{mirror} = 2C - i < C < i\)).

Đánh giá độ phức tạp

Yếu tố Phân tích
Thời gian \(O(N)\) - mỗi vị trí \(i\) chỉ mở rộng khi \(R\) tăng, mà \(R\) tối đa tăng \(2N+1\) lần
Không gian \(O(N)\) - mảng \(P\) độ dài \(2N+1\)

Chứng minh thời gian tuyến tính: Biên phải \(R\) bắt đầu từ 0, chỉ tăng khi mở rộng. Tổng số lần tăng \(R\) qua toàn bộ vòng lặp là \(O(N)\). Mọi lần gán \(P[i] = P[i_{mirror}]\) hoặc \(P[i] = R-i\) đều là \(O(1)\). Do đó tổng thời gian là \(O(N)\).

Code triển khai

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

string preprocess(string s) {
    string t = "^";
    for (char c : s) {
        t += '#';
        t += c;
    }
    t += "#$";
    return t;
}

pair<int,int> manacher(string s) {
    string t = preprocess(s);   // chèn ký tự # để chuyển về palindrome lẻ
    int n = t.length();
    vector<int> P(n, 0);
    int C = 0, R = 0;            // tâm C và biên phải R

    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * C - i; // vị trí đối xứng của i qua C

        if (i < R)                 // tận dụng thông tin đã tính
            P[i] = min(R - i, P[i_mirror]);

        while (t[i + P[i] + 1] == t[i - P[i] - 1])  // mở rộng palindrome
            P[i]++;

        if (i + P[i] > R) {        // cập nhật tâm và biên phải
            C = i;
            R = i + P[i];
        }
    }

    int maxLen = 0, center = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            center = i;
        }
    }

    int start = (center - maxLen) / 2;  // chuyển về chỉ số trong xâu gốc
    return {start, maxLen};
}

int main() {
    string s = "babad";
    auto [start, len] = manacher(s);
    cout << s.substr(start, len) << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def manacher(s):
    t = '^#' + '#'.join(s) + '#$'  # chèn ký tự # để chuyển về palindrome lẻ
    n = len(t)
    p = [0] * n
    c, r = 0, 0                      # tâm C và biên phải R
    for i in range(1, n - 1):
        if i < r:                    # tận dụng thông tin đã tính
            p[i] = min(r - i, p[2 * c - i])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:  # mở rộng palindrome
            p[i] += 1
        if i + p[i] > r:             # cập nhật tâm và biên phải
            c, r = i, i + p[i]
    max_len = max(p)
    center = p.index(max_len)
    start = (center - max_len) // 2  # chuyển về chỉ số trong xâu gốc
    return s[start:start + max_len]

Bước chạy chi tiết

Ví dụ với xâu \(S\) = abba, xâu đã chèn \(T\) = ^#a#b#b#a#$.

\(i\) \(T[i]\) \(i < R\)? Khởi tạo \(P[i]\) Mở rộng \(P[i]\) \(C\) \(R\)
1 # Không 0 t[2]=a vs t[0]=^ khác 0 1 1
2 a Không 0 t[3]=# vs t[1]=# bằng, t[4]=b vs t[0]=^ khác 1 2 3
3 # Không 0 t[4]=b vs t[2]=a khác 0 2 3
4 b Không 0 t[5]=# vs t[3]=# bằng, t[6]=b vs t[2]=a khác 1 4 5
5 # Không 0 t[6]=b vs t[4]=b bằng, t[7]=# vs t[3]=# bằng, t[8]=a vs t[2]=a bằng, t[9]=# vs t[1]=# bằng, t[10]=$ vs t[0]=^ khác 4 5 9
6 b Có (\(6<9\)) \(\min(3, P[4])=\min(3,1)=1\) t[8]=a vs t[4]=b khác 1 5 9
7 # Có (\(7<9\)) \(\min(2, P[3])=\min(2,0)=0\) t[8]=a vs t[6]=b khác 0 5 9
8 a Có (\(8<9\)) \(\min(1, P[2])=\min(1,1)=1\) Mở rộng ra ngoài \(R\), kiểm tra thêm 1 5 9
9 # Không 0 t[10]=$ vs t[8]=a khác 0 5 9

Kết quả: \(P[5]=4\), palindrome dài nhất có tâm tại index 5 trong \(T\), vị trí bắt đầu trong \(S\) là \((5-4)/2=0\), độ dài 4, tức là abba.

Ứng dụng

Bài toán Độ phức tạp Ghi chú
Tìm palindrome dài nhất \(O(N)\) Bài toán cơ bản
Đếm số palindrome con \(O(N)\) Tổng \(\sum P[i] / 2\)
Kiểm tra xâu có palindrome độ dài \(K\) \(O(N)\) Kiểm tra \(\max(P) \geq K\)
Tìm tất cả palindrome \(O(N^2)\) Duyệt và in từ mảng \(P\)
Palindrome dài nhất chứa ký tự tại vị trí \(i\) \(O(N)\) Dùng \(P[i]\)

Lưu ý

  • Manacher chỉ áp dụng cho xâu, không áp dụng cho mảng số
  • Nếu chỉ cần kiểm tra palindrome: Hash xâu cũng được (\(O(N)\))
  • Khi chèn #, độ dài xâu tăng gấp đôi, chú ý bộ nhớ
  • Không cần chèn ^ và $ nếu cẩn thận kiểm tra biên trong code
  • Manacher là thuật toán "hai con trỏ" kết hợp "tận dụng thông tin đã tính"

Bài tập luyện tập

Bài FPTOJ Độ khó Chủ đề
stra-mana Palindrome dài nhất ⭐⭐⭐ Manacher cơ bản
stra-cntpal Đếm palindrome con ⭐⭐⭐ Đếm palindrome
strh-palind Palindrome với Hash ⭐⭐⭐ Palindrome + Hash
strk-kmp Tìm xâu mẫu KMP ⭐⭐ KMP tìm xâu
stra-lcp LCP trên SA ⭐⭐⭐⭐ SA + LCP
man-pk Đếm palindrome độ dài K ⭐⭐⭐ Manacher + đếm
man-cmn Palindrome chung hai vị trí ⭐⭐⭐ Manacher + RMQ
man-cnt Đếm cặp palindrome ⭐⭐⭐ Manacher + đếm
man-even Palindrome độ dài chẵn ⭐⭐⭐ Manacher + chẵn
man-pos Palindrome chứa vị trí ⭐⭐⭐ Manacher + vị trí
man-com Palindrome chung hai xâu ⭐⭐⭐⭐ Manacher + hai xâu
man-odd3 Liệt kê palindrome độ dài 3 ⭐⭐ Manacher + O(N)
man-dst Đếm palindrome phân biệt ⭐⭐⭐ Manacher + Hash

Bài viết liên quan

Tài liệu tham khảo

Bài tiếp theo: Greedy

💬 Bình luận