Mảng Hậu Tố Phép Thuật
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho chuỗi S có độ dài N. Xây dựng mảng hậu tố (suffix array) SA và mảng LCP. Trả lời Q truy vấn: cho mỗi truy vấn là một chuỗi T, tìm số lần xuất hiện của T trong S.
Dữ liệu vào
Dòng 1: Chuỗi S (1 ≤ |S| ≤ 2×10^5), chỉ chữ cái thường Dòng 2: Số nguyên Q (1 ≤ Q ≤ 2×10^5) Q dòng tiếp theo: mỗi dòng một chuỗi T (1 ≤ |T| ≤ |S|) Tổng độ dài các chuỗi T không quá 2×10^5.
Dữ liệu ra
Q dòng, mỗi dòng một số nguyên — số lần xuất hiện của T trong S.
Ví dụ
| Input | Output |
|---|---|
| banana\n3\nana\nan\nban | 2\n2\n1 |
Giới hạn
- 1 ≤ |S| ≤ 2×10^5
- 1 ≤ Q ≤ 2×10^5
- Tổng |T| ≤ 2×10^5
Community Discussion