Tìm Kiếm Mẫu Xâu Bằng Thuật Toán KMP / Z-Function
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Đề 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
Pxuất hiện trongT.
Ví dụ mẫu
Sample Input 1
ababcababa
aba
Sample Output 1
3
Sample Input 2
aaaaa
aa
Sample Output 2
4
Community Discussion