Gợi ý tìm kiếm theo tiền tố

Buổi 55 — Trie & Aho-Corasick
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề 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$.
Draft saved