Đếm xuất hiện mẫu (KMP)

Cho xâu văn bản $S$ độ dài $N$ và xâu mẫu $P$ độ dài $M$, chỉ gồm các chữ cái thường (a–z).

Hãy đếm số lần xâu mẫu $P$ xuất hiện trong $S$ với tư cách là một xâu con liên tiếp. Hai lần xuất hiện được phép chồng lấp (nghĩa là hai vị trí bắt đầu khác nhau đều được tính, ngay cả khi các đoạn của chúng giao nhau).

Dữ liệu vào

• Dòng 1: xâu $S$.
• Dòng 2: xâu mẫu $P$.

Dữ liệu ra

In ra một số nguyên duy nhất là số lần $P$ xuất hiện trong $S$.

Ràng buộc

• $1\le M\le N\le {10}^6$.
• $S$ và $P$ chỉ gồm các chữ cái thường a–z.

Ví dụ

Ghi chú

Với $N$ lên tới ${10}^6$, lời giải kiểm tra mọi vị trí bắt đầu một cách ngây thơ sẽ không đủ nhanh. Hãy nghĩ tới một thuật toán so khớp xâu chạy trong thời gian tuyến tính theo $N+M$.