Xin chào các bạn,

✨ Các bài toán xử lí xâu luôn là chủ đề thú vị trong lập trình thi đấu. Cây tiền tố (Trie) và thuật toán Knuth-Morris-Pratt (KMP) là hai kĩ thuật vốn đã quen thuộc với các lập trình viên. Sự kết hợp của hai chủ đề trên tạo nên một thuật toán cực kì thú vị, đặc biệt trong những bài tập xử lí nhiều xâu - Aho Corasick. Đây là một thuật toán giúp bạn quản lý một tập xâu và giải bài toán kinh điển như sau:

Cho N xâu S[i] và Q xâu T[j]. Với mỗi xâu T[j], liệt kê tất cả các lần xuất hiện của các xâu S[i] ở trong xâu T[j] này.

Hãy cùng VNOI khám phá thuật toán độc đáo này nhé!

🔗 Link bài viết: Aho Corasick

✍️ Người viết: Nguyễn Minh Nhật - HUS High School for Gifted Students

✅ Reviewer:

• Lê Minh Hoàng - Trường Đại học Khoa học Tự nhiên - ĐHQG TP.HCM
• Nguyễn Hoàng Vũ - Trường Đại học Công nghệ - ĐHQGHN

😍 Cảm ơn các bạn TNV & Admin VNOI đã biên soạn bài viết vô cùng bổ ích này. Thông qua bài viết, VNOI hy vọng rằng các bạn sẽ có thể vận dụng linh hoạt kỹ thuật trong quá trình luyện tập cũng như trong các kỳ thi sắp đến. Cảm ơn các bạn đã luôn đồng hành cùng VNOI, hẹn gặp lại các bạn trong các bài viết sau nhé!