Gợi Ý Tự Động

Buổi 55 — Trie & Aho-Corasick
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Một hệ thống tìm kiếm lưu trữ $N$ từ khóa trong từ điển. Với mỗi truy vấn là một xâu tiền tố $P$, hệ thống cần gợi ý từ có thứ tự từ điển nhỏ nhất trong từ điển mà bắt đầu bằng $P$. Nếu không có từ nào thỏa mãn, in ra NONE.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($1 \le N, Q \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa một từ $S_i$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa một xâu tiền tố $P_j$.
Dữ liệu ra
  • Với mỗi truy vấn, in ra từ gợi ý có thứ tự từ điển nhỏ nhất hoặc NONE.
Ví dụ
Input Output
5 4
apple
app
apricot
banana
band
ap
ban
cat
app
app
banana
NONE
app
Giới hạn
  • Tổng độ dài các xâu $S_i$ và $P_j$ không vượt quá $10^6$.
  • Các ký tự đều thuộc a–z.
Draft saved