Cho một xâu văn bản T và một xâu mẫu P. Hãy đếm số vị trí mà P xuất hiện trong T (các lần xuất hiện được phép chồng lấn nhau).
Sử dụng thuật toán KMP với độ phức tạp O(∣T∣+∣P∣).
Ví dụ: T= aaaa, P= aa xuất hiện tại các vị trí bắt đầu 1,2,3 (chồng lấn), nên đáp án là 3.
Dòng đầu chứa xâu T. Dòng thứ hai chứa xâu mẫu P. Cả hai gồm các chữ cái la-tinh thường.
1≤∣P∣≤∣T∣≤106.
In ra một số nguyên là số lần xuất hiện của P trong T.
Ví dụ:
Đầu vào:
aaaa
aa
Đầu ra:
3
Giải thích:
Đang tải editor...