Dò mẫu trong luồng log

Bối cảnh và bài toán

Một hệ thống giám sát lưu toàn bộ chuỗi ký hiệu sự kiện trong một ca vận hành. Bộ phận phân tích có một mẫu cảnh báo ngắn và cần biết mẫu đó xuất hiện bao nhiêu lần trong luồng log, kể cả khi các lần xuất hiện chồng lấn lên nhau.

Yêu cầu

Cho chuỗi log t và mẫu p. Hãy đếm số vị trí bắt đầu mà p xuất hiện trong t.

Input

• Dòng 1 chứa chuỗi t.
• Dòng 2 chứa chuỗi p.

Output

In một số nguyên: số lần p xuất hiện trong t.

Ràng buộc

• 1 <= |t|, |p| <= 2 * 10^5
• Các chuỗi chỉ gồm chữ cái thường a..z.

Chấm điểm

Ví dụ 1

Input

aaaaa
aa

Output

4

Giải thích. Các lần xuất hiện bắt đầu tại vị trí 1, 2, 3, 4 nên có cả trường hợp chồng lấn.

Ví dụ 2

Input

monitoring
ring

Output

1

Giải thích. Mẫu ring chỉ xuất hiện một lần ở cuối chuỗi.

Gợi ý

Hãy thử tìm cách tận dụng kết quả khớp đã biết khi một ký tự mới xuất hiện, thay vì so sánh lại mọi thứ từ đầu.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: CSES Problem Set – String Matching – String Matching (1753).