Đếm Số Lần Xuất Hiện Của Xâu

Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB

Mô tả bài toán

Cho hai xâu ~A~ và ~B~ chỉ gồm các chữ cái tiếng Anh in thường. Bạn hãy đếm số lượng đoạn con (substring) trong xâu ~A~ trùng khớp hoàn toàn với xâu ~B~.

Lưu ý: Các đoạn con được phép giao nhau (chồng chéo vị trí).

Dữ liệu vào (Input)

• Dòng đầu tiên chứa xâu ~A~ (~1 \le |A| \le 10^5~).
• Dòng thứ hai chứa xâu ~B~ (~1 \le |B| \le 10^5~).

Dữ liệu ra (Output)

• In ra một số nguyên duy nhất là số lần xâu ~B~ xuất hiện trong xâu ~A~.

Ví dụ (Examples)

mequangchequangbeonenquangdigiamcan
quang

3

aaaa
aa

3

abcdef
xyz

0

Giải thích (Explanation)

• Ví dụ 1: Từ khóa quang xuất hiện 3 lần trong xâu me[quang]che[quang]beonen[quang]digiamcan.
• Ví dụ 2: Từ khóa aa xuất hiện 3 lần tại các vị trí bắt đầu là 1, 2 và 3. Đây là trường hợp các xâu chồng chéo lên nhau.