Đếm số lần xuất hiện đa mẫu (Aho-Corasick)

Buổi 04 — Mảng 2D & Chuỗi
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề bài

Cho một xâu văn bản $T$ và $K$ xâu mẫu $P_1, P_2, \dots, P_K$ chỉ gồm các chữ cái tiếng Anh thường. Với mỗi xâu mẫu $P_i$, hãy đếm số lần $P_i$ xuất hiện như một xâu con liên tiếp trong $T$ (các lần xuất hiện có thể chồng lên nhau).

Dữ liệu vào
  • Dòng đầu tiên chứa xâu $T$.
  • Dòng thứ hai chứa số nguyên dương $K$.
  • $K$ dòng tiếp theo, mỗi dòng chứa một xâu mẫu $P_i$.
Dữ liệu ra

Gồm $K$ dòng, dòng thứ $i$ ghi số lần xuất hiện của $P_i$ trong $T$.

Ví dụ
Input Output
ababcab
3
ab
ba
aba
3
1
1
Giới hạn

$1 \le |T| \le 2 \cdot 10^5$, $1 \le K \le 5 \cdot 10^4$, tổng độ dài các xâu mẫu không vượt quá $2 \cdot 10^5$.

Draft saved