Tìm Tất Cả Vị Trí Của Nhiều Mẫu
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Đề bài
Cho một chuỗi văn bản $T$ có độ dài $N$ và $M$ chuỗi mẫu $P_1, P_2, \ldots, P_M$. Với mỗi chuỗi mẫu, hãy đếm số lần nó xuất hiện trong $T$.
Sử dụng kỹ thuật double hashing để tránh xung đột.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
- Dòng thứ hai chứa chuỗi $T$ có độ dài $N$.
- $M$ dòng tiếp theo, mỗi dòng chứa một chuỗi mẫu $P_i$.
Dữ liệu ra
- In ra $M$ dòng, dòng thứ $i$ là số lần $P_i$ xuất hiện trong $T$.
Ví dụ
| Input | Output |
|---|---|
| 7 3\nabcabca\nabc\nca\nxyz | 2\n1\n0 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le M \le 10^4$
- $1 \le |P_i| \le N$
- Tổng độ dài các chuỗi mẫu không quá $10^6$
- Các chuỗi chỉ chứa ký tự in thường từ
ađếnz.
Community Discussion