Mảng Hậu Tố Phép Thuật

Buổi 64 — Contest Chặng 7
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved