Cho hai xâu s và t gồm chữ cái thường. Hãy đếm số vị trí trong s mà tại đó bắt đầu một lần xuất hiện của t (các lần xuất hiện được phép chồng lên nhau). Ví dụ t = "aa" xuất hiện 2 lần trong s = "aaa".
Dữ liệu vào
Dòng 1 là xâu s, dòng 2 là xâu t.
Kết quả
Số lần t xuất hiện trong s.
Giới hạn
1 ≤ |t| ≤ |s| ≤ 2000.
Ví dụ 1 – vào
abababa aba
Ví dụ 1 – ra
3
Ví dụ 2 – vào
aaa aa
Ví dụ 2 – ra
2