Đếm Mẫu Trong Văn Bản

Buổi 54 — KMP & Z-function
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu văn bản $T$ và xâu mẫu $P$ chỉ gồm các chữ cái tiếng Anh viết thường. Hãy đếm số lần xâu $P$ 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ể giao nhau).

Dữ liệu vào
  • Dòng 1: xâu $T$ ($1 \le |T| \le 10^6$).
  • Dòng 2: xâu $P$ ($1 \le |P| \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là số lần xuất hiện của $P$ trong $T$.
Ví dụ
Input Output
ababa\naba 2
aaaa\naa 3
Giới hạn
  • $1 \le |T|, |P| \le 10^6$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved