Hướng dẫn giải của Gợi ý từ

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Gợi ý từ

Hướng tiếp cận

Sắp xếp từ điển theo thứ tự từ điển, sau đó dùng tìm kiếm nhị phân để xác định từ đầu tiên khớp với tiền tố. Từ thứ $K$ theo thứ tự từ điển chính là phần tử ở vị trí $first + K - 1$ .

Nhận xét quan trọng

Sau khi sắp xếp từ điển, tất cả các từ bắt đầu bằng tiền tố $p$ tạo thành một đoạn liên tục trong mảng đã sắp xếp.
Từ thứ $K$ khớp với $p$ chính là phần tử ở chỉ số $first\_match + K - 1$ . Ta chỉ cần kiểm tra xem phần tử đó có thực sự bắt đầu bằng $p$ không.
Cần lưu lại chỉ số gốc (1-based) của mỗi từ trước khi sắp xếp.

Thuật toán

Đọc $W$ từ, lưu kèm chỉ số gốc.
Sắp xếp từ theo thứ tự từ điển.
Với mỗi truy vấn (K,p):
- Dùng lower_bound tìm vị trí đầu tiên $\geq p$ .
- Kiểm tra phần tử ở vị trí $first + K - 1$ có bắt đầu bằng $p$ không.
- Nếu có: in ra chỉ số gốc. Nếu không: in ra $- 1$ .

Độ phức tạp

Thời gian: $O (W \log W \cdot L + N \cdot L \cdot \log W)$ với $L$ là độ dài tiền tố tối đa.
Bộ nhớ: $O (W \cdot L_{max})$

Bình luận

Không có bình luận tại thời điểm này.