Thi đấu

Thuật Toán Manacher: Tìm Mọi Xâu Con Đối Xứng Trong O(N)

Thuật toán Manacher là một trong những phát minh đẹp nhất của xử lý chuỗi cho phép tìm bán kính của mọi xâu con đối xứng và xác định chuỗi Palindrome dài nhất trong đúng thời gian tuyến tính O(N).

Thuật Toán Manacher: Tìm Mọi Xâu Con Đối Xứng Trong O(N)

Trong lập trình thi đấu và các kỳ thi tuyển dụng kỹ sư phần mềm cao cấp, chuỗi đối xứng (Palindrome - chuỗi đọc xuôi hay ngược đều hoàn toàn giống nhau) là một chủ đề bài toán vô cùng phổ biến:

  • Kiểm tra tính đối xứng của văn bản.
  • Tìm chuỗi con đối xứng dài nhất (Longest Palindromic Substring).
  • Đếm tổng số lượng chuỗi con đối xứng phân biệt.
  • Phân hoạch văn bản thành số lượng xâu đối xứng ít nhất có thể.

Cách tiếp cận ngây thơ nhất là xét từng vị trí làm tâm và mở rộng sang hai bên. Với một chuỗi có độ dài \(N\), cách làm này tốn thời gian \(O(N^2)\). Khi \(N = 10^5\), cách này ngay lập tức bị loại bỏ vì quá thời gian.

Một cách tiếp cận khác tốt hơn là kết hợp Băm chuỗi (Rolling Hash) và Tìm kiếm nhị phân (Binary Search). Tại mỗi tâm đối xứng, ta nhị phân bán kính đối xứng lớn nhất và dùng mã băm để kiểm tra xem nửa trái có khớp với nửa phải đảo ngược hay không. Kỹ thuật này đạt độ phức tạp \(O(N \log N)\), nhưng đòi hỏi cài đặt cồng kềnh, dễ dính xung đột băm (Hash Collision) và phụ thuộc vào số nguyên tố modulo.

Năm 1975, Glenn K. Manacher công bố một thuật toán tuyến tính tìm các xâu đối xứng nằm ở đầu một xâu; năm 1995, Apostolico, Breslauer và Galil chỉ ra rằng cùng thuật toán đó tìm được mọi xâu đối xứng cực đại ở bất kỳ vị trí nào. Thuật toán mang tên ông: Thuật toán Manacher (Manacher's Algorithm). Thuật toán này có khả năng tìm bán kính đối xứng tại mọi tâm khả dĩ của chuỗi trong đúng thời gian tuyến tính \(O(N)\) và sử dụng đúng \(O(N)\) bộ nhớ, với cấu trúc mã nguồn vô cùng gọn gàng!

Lịch sử và bối cảnh ra đời của thuật toán Manacher

Trước khi thuật toán Manacher được công bố vào năm 1975 trên tạp chí Journal of the ACM, việc tìm kiếm xâu con đối xứng dài nhất trong thời gian tuyến tính được xem là một bài toán vô cùng phức tạp, đòi hỏi phải sử dụng cấu trúc Cây hậu tố (Suffix Tree) của Weiner với dung lượng bộ nhớ khổng lồ. Glenn K. Manacher khi nghiên cứu tại Đại học Illinois đã phát hiện ra rằng: tính chất đối xứng gương cục bộ cho phép tái sử dụng triệt để các kết quả tính toán trước đó mà không cần bất kỳ cấu trúc cây hay con trỏ phức tạp nào. Phát minh mang tính đột phá này đã mở đường cho hàng loạt ứng dụng quan trọng trong phân tích chuỗi gen DNA, nén tệp tin và tìm kiếm mẫu văn bản trong khoa học máy tính hiện đại.

THUẬT TOÁN MANACHER TÌM PALINDROME TRONG O(N) Khai thác tính đối xứng qua tâm C và biên phải R để kế thừa bán kính P[i] = min(R - i, P[i']) Tính chất đối xứng qua tâm C ^ # a # b # a # c # a # b # a # $ VÙNG ĐỐI XỨNG TÂM C Tâm C i' i Biên R i' = 2C - i Bán kính khởi tạo: P[i] = min(R - i, P[i']) Quy tắc và Chứng minh O(N) 1. CHÈN KÝ TỰ ĐẶC BIỆT:s = "aba" → t = "^#a#b#a#$" • Xử lý đồng thời cả độ dài chẵn & lẻ• Chặn '^', '$' chống tràn chỉ số mảng 2. VÌ SAO CHẠY TUYẾN TÍNH O(N)? • Biên phải R chỉ tăng, tới |T| = 2N + 3. • Mỗi phép so sánh mở rộng thành côngđều làm tăng biên R lên ít nhất 1 đơn vị. ⇒ Tổng số phép so sánh ≤ 2(2N + 3) = O(N) KẾT QUẢ THỰC THI:Thời gian: Tuyến tính O(N) hoàn toàn • Bộ nhớ: O(N) • Không có xác suất va chạm hàm băm (Hash collision).
THUẬT TOÁN MANACHER Tìm xâu đối xứng trong thời gian O(N) 1. Biến đổi chèn ký tự '#' "babad" → "^#b#a#b#a#d#$" Xử lý đồng nhất cả palindrome chẵn và lẻ Ký tự '^' và '$' ngăn chặn tràn biên 2. Kế thừa bán kính đối xứng VÙNG ĐỐI XỨNG TÂM C (ĐẾN BIÊN R) i' Tâm C i R CÔNG THỨC KẾ THỪA BÁN KÍNH: P[i] = min(R - i, P[2*C - i]) CHỨNG MINH TUYẾN TÍNH O(N): • Biên R chỉ tăng đơn điệu từ trái qua phải. • Mỗi bước so sánh thành công tăng R lên 1. ⇒ Tổng thời gian chạy đúng O(N)!
Biến đổi xâu chèn ký tự phân cách và cơ chế kế thừa bán kính đối xứng qua tâm C.

Kỹ thuật biến đổi xâu đồng nhất độ dài chẵn và lẻ

Một rắc rối kinh điển khi xử lý xâu đối xứng là phân biệt hai trường hợp:

  1. Xâu đối xứng có độ dài lẻ: Tâm đối xứng là một ký tự duy nhất (ví dụ "aba", tâm là 'b').
  2. Xâu đối xứng có độ dài chẵn: Tâm đối xứng nằm ở "khe giữa" hai ký tự liên tiếp (ví dụ "abba", tâm nằm giữa hai chữ 'b').

Việc phải viết hai hàm riêng biệt để xử lý hai loại tâm khiến mã nguồn bị trùng lặp và rất dễ phát sinh lỗi biên. Glenn Manacher đã giải quyết triệt để rắc rối này bằng một mẹo biến đổi xâu vô cùng thanh lịch:

Chèn một ký tự phân cách đặc biệt # vào đầu, cuối và giữa mọi cặp ký tự liền kề của xâu gốc.

Ngoài ra, để hoàn toàn không bao giờ phải kiểm tra các điều kiện vượt biên mảng (\(i - P[i] \ge 0\) và \(i + P[i] \lt N\)), ta chèn thêm hai ký tự chặn biên (sentinel characters) khác nhau ở hai đầu:

  • Ký tự ^ ở vị trí bắt đầu chuỗi.
  • Ký tự $ ở vị trí kết thúc chuỗi.

Hai ký tự này không bao giờ trùng nhau và không trùng với bất kỳ ký tự nào trong xâu ban đầu.

Ví dụ minh họa biến đổi

Cho chuỗi ban đầu \(S = \text{"abaaba"}\) có độ dài \(N = 6\). Chuỗi sau khi được biến đổi \(T\) sẽ có dạng: T = "^#a#b#a#a#b#a#$" Độ dài của chuỗi \(T\) mới là \(2N + 3\). Mọi xâu đối xứng trong \(S\) (bất kể ban đầu có độ dài chẵn hay lẻ) đều trở thành một xâu đối xứng có độ dài lẻ trong \(T\), với tâm nằm chính xác tại một vị trí ký tự nào đó trên \(T\)!

Mối quan hệ toán học tuyệt đẹp: Nếu tại chỉ số \(i\) trên chuỗi \(T\), bán kính đối xứng lớn nhất là \(P[i]\) (nghĩa là đoạn đối xứng dài nhất xung quanh \(i\) kéo dài từ \(i - P[i]\) đến \(i + P[i]\)), thì: Độ dài của xâu đối xứng tương ứng trong chuỗi gốc \(S\) chính bằng đúng \(P[i]\)!

Ý tưởng cốt lõi: Kế thừa tính đối xứng qua tâm C

Gọi \(P[i]\) là bán kính đối xứng lớn nhất tại tâm \(i\) trên chuỗi biến đổi \(T\). Trong quá trình duyệt \(i\) từ trái sang phải, ta luôn duy trì hai biến toàn cục:

  • \(C\) (Center): Tâm của xâu con đối xứng đang có biên phải vươn xa nhất về phía bên phải.
  • \(R\) (Right edge): Vị trí biên phải xa nhất của xâu đối xứng có tâm tại \(C\) (\(R = C + P[C]\)).

Khi ta đang cần tính giá trị \(P[i]\) cho vị trí \(i\):

Trường hợp 1: Vị trí \(i\) nằm ngoài vùng kiểm soát (\(i \ge R\))

Nếu \(i\) nằm ngoài hoặc trùng với biên phải \(R\), ta chưa có bất kỳ thông tin nào được bảo đảm trước đó. Ta bắt đầu với \(P[i] = 0\) và dùng vòng lặp mở rộng hai bên từng bước một: Khi \(T[i - 1 - P[i]] == T[i + 1 + P[i]]\), ta tăng \(P[i]\) lên \(1\).

Trường hợp 2: Vị trí \(i\) nằm bên trong vùng kiểm soát (\(i \lt R\))

Đây chính là trái tim của thuật toán Manacher: Vì đoạn từ \(C - P[C]\) đến \(C + P[C]\) (tức đoạn \([L, R]\)) là một xâu đối xứng với tâm tại \(C\), nên mọi tính chất ở nửa bên phải tâm \(C\) đều được phản chiếu đối xứng hoàn hảo sang nửa bên trái tâm \(C\)!

Gọi \(i'\) là điểm đối xứng của \(i\) qua tâm \(C\): \[i' = 2C - i\] Vì \(i'\) nằm trước \(i\), giá trị bán kính \(P[i']\) đã được tính toán hoàn tất từ các bước trước đó. Ta có ba khả năng xảy ra đối với vị trí \(i'\):

  1. Hộp đối xứng của \(i'\) nằm hoàn toàn bên trong \([L, R]\) (\(P[i'] \lt R - i\)): Do tính đối xứng gương hoàn hảo qua \(C\), bán kính tại \(i\) chắc chắn phải bằng đúng bán kính tại \(i'\): \[P[i] = P[i']\] Ta không cần thực hiện thêm bất kỳ phép so sánh ký tự nào!
  2. Hộp đối xứng của \(i'\) vượt ra ngoài biên trái \(L\) (\(P[i'] \gt R - i\)): Phần nằm bên trong \([L, R]\) chắc chắn đối xứng, nhưng phần vượt ra ngoài \(L\) không được bảo đảm đối xứng với phần vượt ra ngoài \(R\). Do đó, bán kính tại \(i\) ít nhất phải bằng khoảng cách tới biên phải: \[P[i] = R - i\]
  3. Hộp đối xứng của \(i'\) chạm đúng vào biên trái \(L\) (\(P[i'] == R - i\)): Bán kính tại \(i\) ít nhất bằng \(R - i\), và có thể còn mở rộng xa hơn nữa ra ngoài biên \(R\). Ta khởi tạo \(P[i] = R - i\) và tiếp tục dùng vòng lặp thử mở rộng thêm.

Tổng kết lại cả ba khả năng, ta có công thức khởi tạo khởi điểm cực kỳ ngắn gọn: \[P[i] = \min(R - i, P[2C - i])\]

Sau khi khởi tạo \(P[i]\), ta chỉ việc chạy vòng lặp mở rộng tiếp nếu có thể. Sau đó, nếu biên phải mới \(i + P[i]\) vượt qua biên phải kỷ lục cũ \(R\), ta cập nhật lại tâm mới: \(C = i\) và \(R = i + P[i]\).

Chứng minh độ phức tạp thời gian tuyến tính O(N)

Tại sao thuật toán Manacher lại đạt độ phức tạp tuyến tính \(O(N)\) dù bên trong có chứa vòng lặp while mở rộng ký tự?

Hãy quan sát sự biến thiên của biến \(R\):

  • Mỗi khi vòng lặp while so sánh thành công hai ký tự khớp nhau, nó mở rộng biên phải của đoạn đối xứng hiện tại sang phải ít nhất 1 đơn vị.
  • Nếu việc mở rộng này làm cho \(i + P[i] \gt R\), biến \(R\) sẽ được tăng lên giá trị mới lớn hơn.
  • Mỗi phép so sánh ký tự thành công luôn làm tăng giá trị của \(R\) lên ít nhất 1 đơn vị!
  • Vì \(R\) chỉ di chuyển từ \(0\) đến độ dài chuỗi \(|T| = 2N + 3\) và không bao giờ giảm lùi, tổng số lần so sánh ký tự thành công trên toàn bộ thuật toán bị chặn trên bởi \(2N + 3\).
  • Mặt khác, tại mỗi vị trí \(i\), vòng lặp while chỉ có thể gặp tối đa đúng 1 lần so sánh thất bại (ký tự không khớp) trước khi bị ngắt. Với \(2N + 3\) vị trí, tổng số lần so sánh thất bại tối đa là \(2N + 3\).

Do đó, tổng số phép so sánh ký tự trong toàn bộ thuật toán không bao giờ vượt quá \(2(2N + 3) = O(N)\). Thuật toán Manacher đạt độ phức tạp thời gian chính xác là \(O(N)\) tuyến tính!

Mô phỏng chi tiết từng bước trên xâu mẫu

Để hiểu sâu sắc cơ chế hoạt động của thuật toán Manacher, ta hãy quan sát bảng trạng thái từng bước khi thuật toán xử lý chuỗi ban đầu \(S = \text{"aba"}\):

Sau khi biến đổi, ta có chuỗi T = "^#a#b#a#$" với độ dài 9 ký tự, các chỉ số từ 0 đến 8:

  • Khởi tạo ban đầu: \(C = 0, R = 0\), mảng \(P\) gồm toàn số 0.
  • Tại \(i = 1\) (\(T[1] = \text{'#'}\)): Vì \(i \ge R\), ta mở rộng trực tiếp. Ký tự trước \(T[0] = \text{'^'}\) khác \(T[2] = \text{'a'}\), vòng lặp dừng ngay. \(P[1] = 0\).
  • Tại \(i = 2\) (\(T[2] = \text{'a'}\)): \(i \ge R\), mở rộng sang hai bên: \(T[1] = T[3] = \text{'#'}\) khớp nhau; tiếp theo \(T[0] = \text{'^'}\) khác \(T[4] = \text{'b'}\) nên dừng. Bán kính đạt \(P[2] = 1\). Cập nhật biên kỷ lục mới: \(C = 2, R = 2 + 1 = 3\).
  • Tại \(i = 3\) (\(T[3] = \text{'#'}\)): Vì \(i = R = 3\), ta mở rộng trực tiếp: \(T[2] = \text{'a'}\) khác \(T[4] = \text{'b'}\), dừng. \(P[3] = 0\).
  • Tại \(i = 4\) (\(T[4] = \text{'b'}\)): \(i \ge R\), mở rộng sang hai bên: \(T[3] = T[5] = \text{'#'}\) (khớp); \(T[2] = T[6] = \text{'a'}\) (khớp); \(T[1] = T[7] = \text{'#'}\) (khớp); \(T[0] = \text{'^'}\) khác \(T[8]\) (ký tự chặn cuối) nên dừng. Bán kính đạt \(P[4] = 3\). Cập nhật biên kỷ lục mới: \(C = 4, R = 4 + 3 = 7\).
  • Tại \(i = 5\) (\(T[5] = \text{'#'}\)): Vì \(i \lt R\) (\(5 \lt 7\)), ta kế thừa qua tâm \(C = 4\). Điểm đối xứng \(i' = 2 \times 4 - 5 = 3\). Giá trị \(P[3] = 0 \lt R - i = 2\). Do đó \(P[5] = P[3] = 0\) ngay lập tức mà không cần so sánh bất kỳ ký tự nào!
  • Tại \(i = 6\) (\(T[6] = \text{'a'}\)): Vì \(i \lt R\) (\(6 \lt 7\)), kế thừa qua tâm \(C = 4\). Điểm đối xứng \(i' = 2 \times 4 - 6 = 2\). Giá trị \(P[2] = 1 == R - i = 1\). Bán kính khởi điểm là \(P[6] = 1\). Thử mở rộng tiếp: \(T[4] = \text{'b'}\) khác \(T[8]\) (ký tự chặn cuối), dừng. Kết quả \(P[6] = 1\).

Giá trị lớn nhất trong mảng \(P\) là \(P[4] = 3\), tương ứng với xâu con đối xứng dài nhất có độ dài bằng 3 là \(\text{"aba"}\)!

So sánh toàn diện các phương pháp tìm xâu đối xứng

Phương pháp Độ phức tạp thời gian Bộ nhớ phụ trợ Ưu điểm nổi bật Nhược điểm phòng thi
Duyệt trâu mọi tâm \(O(N^2)\) \(O(1)\) Cực kỳ dễ nhớ, không lỗi Quá thời gian khi \(N\) cỡ \(10^5\) (xâu toàn ký tự giống nhau)
Rolling Hash + Nhị phân \(O(N \log N)\) \(O(N)\) Dễ mở rộng cho truy vấn đoạn Dễ bị hack tràn số, xung đột modulo
Thuật toán Manacher \(O(N)\) tuyến tính \(O(N)\) Tối ưu tuyệt đối, cài đặt 25 dòng Chỉ áp dụng cho xâu tĩnh
Cây Palindrome (EERTREE) \(O(N \cdot \Sigma)\) \(O(N \cdot \Sigma)\) Xử lý xâu trực tuyến, đếm tần số Cài đặt rất dài, tốn nhiều bộ nhớ
Học cùng giảng viên

Chủ đề này nằm trong Buổi 09 - KMP, Z-function, Trie & Rolling Hash của Tài năng lập trình. Xem đề cương

Các biến thể bài toán Palindrome nâng cao trong kỳ thi ICPC

  1. Tìm tiền tố hoặc hậu tố đối xứng dài nhất (Longest Palindromic Prefix/Suffix): Một bài toán thường gặp: Cho chuỗi \(S\), hãy thêm vào đầu chuỗi \(S\) số ký tự ít nhất để thu được một chuỗi đối xứng hoàn chỉnh. Để số ký tự thêm vào là ít nhất, phần đầu có sẵn của chuỗi \(S\) (tiền tố) phải là một chuỗi đối xứng có độ dài lớn nhất: ta chỉ cần chép ngược phần còn lại lên trước. Bằng cách áp dụng thuật toán Manacher trên chuỗi \(T\), ta chỉ cần tìm bán kính đối xứng lớn nhất tại một tâm \(i\) sao cho xâu con đối xứng bắt đầu đúng từ ký tự đầu tiên của chuỗi (\(i - P[i] == 1\)). Độ dài phần còn lại cần thêm vào đầu chuỗi chính là \(N - P[i]\). Ví dụ \(S = \text{"baa"}\): tiền tố đối xứng dài nhất là \(\text{"b"}\), nên phải thêm 2 ký tự để được \(\text{"aabaa"}\). Nếu đề bài cho thêm ký tự vào cuối chuỗi, ta làm ngược lại với hậu tố đối xứng dài nhất (\(i + P[i] == |T| - 2\)). Toàn bộ bài toán được giải quyết trong đúng \(O(N)\) thời gian!

  2. Bài toán đếm số chuỗi đối xứng chẵn lẻ độc lập: Nhiều đề bài phân tách riêng biệt số lượng chuỗi đối xứng độ dài chẵn và chuỗi đối xứng độ dài lẻ. Nhờ mảng \(P\) trên chuỗi biến đổi \(T\):

    • Các tâm \(i\) là vị trí lẻ (ứng với ký tự phân cách #) sinh ra toàn bộ các chuỗi đối xứng có độ dài chẵn trong xâu gốc.
    • Các tâm \(i\) là vị trí chẵn (ứng với ký tự thực) sinh ra toàn bộ các chuỗi đối xứng có độ dài lẻ trong xâu gốc. Ta chỉ cần tách biệt vòng lặp tính tổng theo tính chẵn lẻ của chỉ số tâm \(i\) trong đúng một lượt duyệt \(O(N)\).

Cẩm nang chuyển đổi chỉ số và tránh lỗi Off-by-one

Một trong những trở ngại lớn nhất khi triển khai thuật toán Manacher trong phòng thi là việc chuyển đổi ngược từ chỉ số trên chuỗi biến đổi \(T\) về chuỗi gốc \(S\).

Giả sử tại tâm \(i\) trên chuỗi \(T\), ta có bán kính đối xứng lớn nhất là \(P[i]\):

  • Đoạn xâu đối xứng trên chuỗi \(T\) có biên trái là \(i - P[i]\) và biên phải là \(i + P[i]\).
  • Vì các ký tự ở hai biên \(i - P[i]\) và \(i + P[i]\) luôn là ký tự phân cách # (hoặc ký tự chặn), các ký tự thực sự thuộc chuỗi gốc \(S\) sẽ bắt đầu từ chỉ số: \[\mathrm{start} = \left\lfloor \frac{i - P[i]}{2} \right\rfloor\]
  • Độ dài thực sự của xâu con đối xứng trong chuỗi gốc \(S\) chính bằng đúng giá trị bán kính \(P[i]\).
  • Chuỗi con đối xứng tìm được trong \(S\) sẽ là: \[S[\mathrm{start} \dots \mathrm{start} + P[i] - 1]\]

Công thức chuyển đổi trực tiếp này áp dụng chính xác cho cả hai trường hợp xâu đối xứng độ dài chẵn và xâu đối xứng độ dài lẻ mà không cần phân nhánh if-else. Việc nắm vững công thức này giúp bạn trích xuất chuỗi con kết quả trong \(O(1)\) mà không bao giờ bị dính lỗi lệch 1 vị trí (Off-by-one Error).

Bảng tóm tắt các tính chất đối xứng quan trọng

Khi giải các bài toán xâu đối xứng trong các kỳ thi Học sinh giỏi và ICPC, việc ghi nhớ các đặc điểm sau giúp bạn xây dựng thuật toán nhanh chóng:

  • Một xâu độ dài \(N\) có tối đa \(N\) xâu con đối xứng phân biệt.
  • Mọi xâu con đối xứng đều có thể biểu diễn qua tâm và bán kính đối xứng \(P[i]\).
  • Bán kính đối xứng tại các tâm luôn thỏa mãn tính chất gương qua tâm bao phủ \(C\).
  • Tổng độ dài các xâu con đối xứng dài nhất có thể tính trực tiếp bằng mảng tiền tố trên mảng \(P\).

Tư duy phân tích bài toán chuỗi đối xứng trong phòng thi

Khi đọc đề bài liên quan đến chuỗi đối xứng trong phòng thi, học sinh giỏi cần xác định nhanh chiến lược tiếp cận phù hợp:

  1. Nếu bài toán yêu cầu đếm hoặc tìm xâu con đối xứng dài nhất trên xâu tĩnh: Thuật toán Manacher là lựa chọn số một vì cài đặt chỉ tốn khoảng 25 dòng mã nguồn, thời gian chạy tuyến tính \(O(N)\) tuyệt đối và không phụ thuộc vào bất kỳ hằng số modulo nào.
  2. Nếu bài toán có thêm thao tác sửa đổi ký tự hoặc thêm ký tự trực tuyến (Online Queries): Lúc này Manacher không hỗ trợ trực tiếp. Bạn nên cân nhắc chuyển sang cấu trúc Băm chuỗi (Rolling Hash) kết hợp Cây phân đoạn (Segment Tree) hoặc Cây Palindrome (Palindromic Tree).
  3. Nếu bài toán yêu cầu truy vấn nhiều đoạn con \([L, R]\): Kết hợp Manacher với Bảng thưa (Sparse Table) hoặc Segment Tree để tìm tâm có bán kính bao phủ đoạn con trong thời gian \(O(1)\) hoặc \(O(\log N)\).

Cài đặt chuẩn C++17 và Python 3

Dưới đây là lời giải hoàn chỉnh của thuật toán Manacher, tìm độ dài xâu con đối xứng dài nhất và trả về vị trí xuất hiện:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// Thuật toán Manacher tìm mọi xâu con đối xứng trong O(N)
// Trả về {độ dài lớn nhất, vị trí bắt đầu trên xâu gốc}
pair<int, int> manacher(const string& s) {
    if (s.empty()) return {0, 0};

    // Chuyển đổi xâu: xen kẽ ký tự '#' và thêm chặn biên '^', '$'
    string t = "^#";
    for (char ch : s) {
        t += ch;
        t += '#';
    }
    t += '$';

    int m = (int)t.size();
    vector<int> p(m, 0);
    int c = 0, r = 0;

    for (int i = 1; i < m - 1; i++) {
        int i_mirror = 2 * c - i;

        if (r > i) {
            p[i] = min(r - i, p[i_mirror]);
        } else {
            p[i] = 0;
        }

        // Mở rộng xâu đối xứng tâm i
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
            p[i]++;
        }

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

    int max_len = 0;
    int center_idx = 0;
    for (int i = 1; i < m - 1; i++) {
        if (p[i] > max_len) {
            max_len = p[i];
            center_idx = i;
        }
    }

    int start_pos = (center_idx - max_len) / 2;
    return {max_len, start_pos};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    if (!(cin >> s)) return 0;

    auto [max_len, start_pos] = manacher(s);

    cout << max_len << "\n";
    cout << s.substr(start_pos, max_len) << "\n";

    return 0;
}

Các ứng dụng mở rộng của thuật toán Manacher

  1. Đếm tổng số xâu con đối xứng trong thời gian O(N): Với mỗi vị trí \(i\) trên chuỗi biến đổi \(T\), độ dài bán kính \(P[i]\) đóng góp đúng \(\lfloor (P[i] + 1) / 2 \rfloor\) xâu con đối xứng cho chuỗi gốc \(S\). Tổng số xâu con đối xứng của toàn bộ chuỗi \(S\) chỉ là tổng tích lũy của các giá trị này trong một vòng lặp \(O(N)\) duy nhất!
  2. Tìm xâu đối xứng dài nhất bắt đầu hoặc kết thúc tại mỗi vị trí: Kết hợp mảng \(P\) với cấu trúc Segment Tree hoặc kỹ thuật cập nhật đoạn, ta có thể xác định xâu đối xứng dài nhất kết thúc tại chỉ số \(i\) với mọi \(i \in [0, N - 1]\).
  3. Phân hoạch xâu thành số xâu đối xứng ít nhất (Palindromic Partitioning): Bài toán quy hoạch động: Tìm số lần cắt ít nhất để chia chuỗi thành các xâu con đối xứng. Kết hợp Manacher để tiền xử lý tính đối xứng của mọi đoạn con \([l, r]\) giúp thuật toán quy hoạch động chạy trong \(O(N^2)\) thay vì \(O(N^3)\).
  4. Phát hiện chuỗi đối xứng trên cây (Palindromic Paths on Trees): Trong các kỳ thi lập trình quốc tế nâng cao, bài toán tìm đường đi đơn dài nhất trên cây có nhãn các cạnh tạo thành chuỗi đối xứng là một thử thách lớn. Bằng cách kết hợp thuật toán Manacher với phân rã trọng tâm (Centroid Decomposition) hoặc trải phẳng cây Euler Tour, ta có thể kiểm tra tính đối xứng của các đường đi qua trọng tâm một cách hiệu quả, giảm độ phức tạp thời gian từ \(O(N^3)\) của cách duyệt mọi đường đi về \(O(N \log^2 N)\).
  5. Kỹ thuật nén dữ liệu dựa trên chuỗi đối xứng: Trong lý thuyết nén dữ liệu, việc nhận diện và thay thế các chuỗi con đối xứng lặp lại bằng các con trỏ tham chiếu ngắn hơn (tương tự thuật toán LZ77) giúp giảm đáng kể kích thước tệp lưu trữ. Mảng bán kính \(P[i]\) của Manacher cung cấp thông tin toàn cảnh về mọi vị trí đối xứng tiềm năng trong thời gian tuyến tính.

Phân tích trường hợp biên và độ ổn định thực thi

Thuật toán Manacher có khả năng xử lý an toàn và chính xác tuyệt đối mọi trường hợp dữ liệu biên đặc biệt:

  • Chuỗi có độ dài bằng 1: Mảng \(P\) xác định bán kính đúng bằng 1 tại ký tự duy nhất, thuật toán kết luận chính xác chuỗi con đối xứng dài nhất có độ dài bằng 1.
  • Chuỗi gồm toàn ký tự giống nhau (ví dụ "aaaaa"): Bán kính đối xứng tại tâm chính giữa đạt giá trị tối đa bằng độ dài chuỗi \(N\). Các bước kế thừa đối xứng qua tâm \(C\) hoạt động trơn tru mà không làm suy biến độ phức tạp thời gian.
  • Ký tự chặn biên bảo vệ an toàn bộ nhớ: Nhờ việc đặt hai ký tự chặn khác biệt (dấu mũ '^' ở đầu và dấu đô la '$' ở cuối), vòng lặp while so sánh ký tự luôn luôn gặp điều kiện dừng tự nhiên khi chạm tới hai đầu mút của chuỗi biến đổi T. Lập trình viên hoàn toàn không phải bổ sung bất kỳ câu lệnh kiểm tra cận biên chỉ số nào bên trong vòng lặp chính, vừa giúp mã nguồn ngắn gọn, thanh lịch, vừa tăng tốc độ thực thi đáng kể nhờ loại bỏ các lệnh rẽ nhánh điều kiện không cần thiết trên đường ống vi xử lý hiện đại.

Ứng dụng thực tế trong sinh học phân tử và giải trình tự gen

Trong lĩnh vực tin sinh học (Bioinformatics), thuật toán Manacher đóng vai trò nền tảng trong việc phân tích các chuỗi nucleotide DNA và RNA:

  1. Phát hiện cấu trúc vòng kẹp tóc (Hairpin Loops): Các phân tử RNA đơn thường có xu hướng tự gập lại tạo thành cấu trúc bậc hai dạng kẹp tóc, trong đó hai đoạn nucleotide đối xứng liên kết hydro với nhau theo nguyên tắc bổ sung. Thuật toán Manacher mở rộng cho phép quét qua các chuỗi gen dài hàng triệu ký tự để xác định chính xác các vùng có khả năng tự bắt cặp đối xứng trong thời gian thực.
  2. Vị trí nhận diện của enzyme cắt giới hạn (Restriction Sites): Các enzyme giới hạn trong vi khuẩn thường nhận diện các đoạn trình tự palindrome ngắn (từ 4 đến 8 cặp base) để thực hiện cắt liên kết phosphodiester. Lưu ý: palindrome trong sinh học là đoạn bằng chuỗi bù đảo ngược của nó, không phải xâu đọc xuôi ngược như nhau. Ví dụ vị trí nhận diện của enzyme EcoRI là GAATTC: đảo ngược thành CTTAAG, lấy bù từng base (A với T, C với G) lại được GAATTC. Muốn dùng Manacher cho việc này, ta thay phép so sánh hai ký tự bằng phép kiểm tra hai base có bù nhau hay không; khi đó thuật toán liệt kê được mọi đoạn có thể là vị trí nhận diện của enzyme giới hạn.

Luyện ngay trên Big-O Coding

Để củng cố kiến thức và kiểm tra trực tiếp độ chính xác của chương trình, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

Thuật toán Manacher có chạy được với bảng chữ cái Unicode tiếng Việt không?

Hoàn toàn được! Miễn là các ký tự phân cách như #, ^, $ không xuất hiện trong bảng mã đầu vào. Trong C++, bạn nên dùng chuỗi ký tự rộng std::wstring hoặc vector số nguyên std::vector để lưu trữ mã Unicode của từng ký tự tiếng Việt thay vì dùng kiểu std::string 8-bit.

Cây Palindrome (EERTREE / Palindromic Tree) khác gì so với Manacher?
  • Thuật toán Manacher: Tìm xâu đối xứng tại mọi vị trí tâm trong xâu tĩnh, cấu trúc mã nguồn cực kỳ ngắn gọn (khoảng 20 dòng) và tiết kiệm bộ nhớ tối đa.
  • Cây Palindrome (EERTREE): Một cấu trúc dữ liệu đồ thị có hướng quản lý toàn bộ các xâu con đối xứng phân biệt. Hỗ trợ thêm ký tự trực tuyến (Online Processing), đếm tần số xuất hiện của từng xâu palindrome, nhưng cài đặt phức tạp hơn đáng kể.
Có thể kiểm tra một đoạn con bất kỳ [L, R] có phải là palindrome trong O(1) bằng Manacher không?

Có thể được! Đoạn con \([L, R]\) trong chuỗi gốc \(S\) có tâm nằm tại vị trí \(mid = L + R + 2\) trên chuỗi biến đổi \(T\) (với \(S\) đánh số từ 0 và \(T\) có ký tự chặn ở vị trí 0 như trong code). Độ dài đoạn là \(len = R - L + 1\). Đoạn \([L, R]\) là một palindrome khi và chỉ khi bán kính đối xứng tại tâm đó thỏa mãn: \(P[mid] \ge len\). Phép kiểm tra này thực hiện hoàn toàn trong đúng \(O(1)\)!

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483