Gợi ý từ

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í $\text{first}+K-1$.

Nhận xét quan trọng

1. 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.
2. Từ thứ $K$ khớp với $p$ chính là phần tử ở chỉ số $\text{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.
3. 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

1. Đọc $W$ từ, lưu kèm chỉ số gốc.
2. Sắp xếp từ theo thứ tự từ điển.
3. Với mỗi truy vấn $(K,p)$:
   • Dùng lower_bound tìm vị trí đầu tiên $\ge p$.
   • Kiểm tra phần tử ở vị trí $\text{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·L+N·L·\log W)$ với $L$ là độ dài tiền tố tối đa.
• Bộ nhớ: $O(W·L_{max})$