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 xác định thông tin nào có thể được duy trì khi quét từng ký tự hoặc khi đi qua từng node prefix, thay vì xử lý lại toàn bộ chuỗi/tập từ sau mỗi thao tác.

Thông tin bài tập

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