Đếm số lần xuất hiện đa mẫu (Aho-Corasick)
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề 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$.
Community Discussion