Tìm Tất Cả Vị Trí Của Nhiều Mẫu

Buổi 53 — String Hashing
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề 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 đến z.
Draft saved