Bình muốn đếm số lần xuất hiện của xâu mẫu \(P\) trong văn bản \(T\). Các lần xuất hiện có thể chồng chéo lên nhau. Ví dụ, trong aaaa, mẫu aa xuất hiện 3 lần (tại vị trí 0, 1, 2). Hãy dùng KMP để đếm.

Định dạng đầu vào

• Dòng đầu chứa xâu \(T\).
• Dòng thứ hai chứa xâu \(P\).
• Độ dài các xâu không quá \(10^5\), chỉ gồm chữ cái in thường.

Định dạng đầu ra

• Một số nguyên duy nhất là số lần xuất hiện.

Ví dụ

Input:

aaaa
aa

Output:

3

Ràng buộc

• 100% số điểm: \(|T|, |P| \le 10^5\).