Gợi ý tìm kiếm theo tiền tố
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Một công cụ tìm kiếm lưu trữ một từ điển gồm $N$ từ khóa (các từ khóa có thể trùng nhau, chỉ gồm các chữ cái tiếng Anh viết thường). Khi người dùng gõ $Q$ truy vấn, mỗi truy vấn là một xâu tiền tố $P$, hãy cho biết có bao nhiêu từ khóa trong từ điển bắt đầu bằng tiền tố $P$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
- $N$ dòng tiếp theo, mỗi dòng chứa một từ khóa trong từ điển.
- $Q$ dòng tiếp theo, mỗi dòng chứa một xâu tiền tố $P$.
Dữ liệu ra
- In ra $Q$ dòng là số lượng từ khóa khớp với từng tiền tố.
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 5 3 apple app apricot banana app app ap cat |
3 4 0 |
Giới hạn
- $1 \le N, Q \le 10^5$
- Tổng độ dài các từ khóa và các truy vấn không vượt quá $5 \cdot 10^5$.
Community Discussion