Phân Tích Đa Văn Bản
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Đề bài
Cho $N$ xâu mẫu $P_1, P_2, \dots, P_N$ và $M$ xâu văn bản $T_1, T_2, \dots, T_M$. Với mỗi xâu mẫu $P_i$, hãy đếm xem có bao nhiêu văn bản $T_j$ ($1 \le j \le M$) chứa $P_i$ như một xâu con (mỗi văn bản chỉ được tính tối đa 1 lần cho mỗi mẫu, ngay cả khi mẫu xuất hiện nhiều lần trong văn bản đó).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N, M \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa một xâu mẫu $P_i$.
- $M$ dòng tiếp theo, mỗi dòng chứa một xâu văn bản $T_j$.
Dữ liệu ra
- Gồm $N$ dòng, dòng thứ $i$ là số lượng văn bản chứa $P_i$.
Ví dụ
| Input | Output |
|---|---|
| 3 3 a aa ab aaaa abab bbb |
2 1 1 |
Giới hạn
- Tổng độ dài các xâu mẫu không vượt quá $2 \cdot 10^5$.
- Tổng độ dài các văn bản không vượt quá $2 \cdot 10^5$.
- Các ký tự đều thuộc
a–z.
Community Discussion