Phân Tích Đa Văn Bản

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