Tìm Kiếm Mẫu Xâu Bằng Thuật Toán KMP / Z-Function

Algorithms Buổi 54 — KMP & Z-function Strings
Points
30
AC Rate
0.0%
Time limit
1.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 thường (a-z). Hãy đếm số lần xâu mẫ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ể chồng lấp nhau).

Dữ liệu vào (Input)
  • Dòng 1: Xâu văn bản T (1 ≤ |T| ≤ 5 × 10^5).
  • Dòng 2: Xâu mẫu P (1 ≤ |P| ≤ |T|).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là số lần P xuất hiện trong T.
Ví dụ mẫu
Sample Input 1
ababcababa
aba
Sample Output 1
3
Sample Input 2
aaaaa
aa
Sample Output 2
4
Draft saved