🖐️ VNOI xin chào các bạn,

👉 Ở các bài viết trước của VNOI Wiki Project, chúng ta đã được tìm hiểu nhiều thuật toán cũng như kỹ thuật trong xử lý xâu như thuật toán KMP hay hàm Z (Z-function). Trong bài viết này, VNOI sẽ mang đến cho các bạn một thuật toán khác cũng quan trọng không kém trong các kỳ thi lập trình thi đấu – thuật toán Manacher.

👉 Thuật toán Manacher là một thuật toán rất hiệu quả khi giải quyết các bài toán về tìm xâu con đối xứng. Bằng cách tận dụng các dữ liệu có sẵn, thuật toán Manacher có thể tối ưu độ phức tạp của thuật giải xuống còn O(n), tức trong thời gian tuyến tính. Đặc biệt, mặc dù thuật toán Manacher ít được phổ biến, nhưng đây là một thuật toán có ý tưởng rất tự nhiên cũng như rất dễ cài đặt nên sẽ rất có ích trong các cuộc thi lập trình thi đấu.

👉 Để tìm hiểu chi tiết hơn về thuật toán này, các bạn hãy cùng đọc qua bài viết này trên VNOI Wiki nhé!

🔗 Link bài viết: Tại đây.

✍️ Biên soạn: Phạm Hoàng Hiệp – University of Georgia.

✅ Reviewer:

• Nguyễn Minh Hiển - Trường Đại học Công nghệ, ĐHQGHN
• Nguyễn Minh Nhật - Trường THPT chuyên Khoa học Tự nhiên, ĐHQGHN
• Ngô Nhật Quang - The University of Texas at Dallas

😍 Xin cảm ơn các bạn TNV cùng admin VNOI đã biên soạn và hoàn thiện bài viết này. Chúng mình hy vọng rằng qua bài viết này các bạn sẽ có thêm một công cụ hiệu quả trong các bài toán xử lý xâu. Chúc các bạn luyện tập thật hiệu quả, hẹn gặp lại các bạn trong các bài viết sau!