Cây tiền tố Trie: Từ điển tra cứu và đếm tiền tố

Mục tiêu kiến thức

• Nắm vững cấu trúc dữ liệu Cây tiền tố (Trie).
• Cài đặt các thao tác chèn từ, tra cứu từ hoàn chỉnh trong O(|S|).
• Mở rộng cấu trúc Trie để đếm số từ có chung một tiền tố trong O(|P|).

Mô tả bài toán

Bộ máy gợi ý thông minh (Auto-complete Search) của AI Empire Academy cần tối ưu hóa tốc độ phản hồi khi học viên tìm kiếm thuật toán. Bạn được giao xây dựng cấu trúc Cây tiền tố (Trie) để quản lý tập từ điển và trả lời nhanh Q truy vấn thuộc 3 loại:

• 1 S: Thêm xâu ký tự S vào từ điển.
• 2 S: Kiểm tra xem xâu S có tồn tại dưới dạng một từ hoàn chỉnh trong từ điển không. In YES nếu có, ngược lại in NO.
• 3 P: Đếm số lượng từ hiện có trong từ điển có tiền tố là P. In ra một số nguyên là kết quả đếm.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ Q ≤ 10⁵.
• Tổng độ dài các xâu ≤ 5 · 10⁵.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.