Đếm xuất hiện không chồng lấp

Cho hai xâu $S$ và $P$ chỉ gồm chữ cái thường. Một xuất hiện của $P$ trong $S$ là một vị trí $i$ sao cho $S[i\dots i+|P|-1]=P$ (chỉ số tính từ $1$).

Hãy đếm số xuất hiện không chồng lấp lớn nhất có thể chọn của $P$ trong $S$. Hai xuất hiện tại vị trí $i$ và $j$ (với $i<j$) gọi là không chồng lấp nếu $j\ge i+|P|$.

Có thể chứng minh rằng số lượng tối đa đạt được nhờ chiến lược tham lam: quét $S$ từ trái sang phải, mỗi khi gặp xuất hiện thì lấy luôn và bỏ qua $|P|$ ký tự của xuất hiện đó.

Dữ liệu vào

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

Dữ liệu ra

Một số nguyên duy nhất: số xuất hiện không chồng lấp tối đa.

Ràng buộc

• $1\le |S|,|P|\le {10}^6$
• Cả $S$ và $P$ chỉ gồm chữ cái Latin thường (a–z).

Ví dụ

Ghi chú

• Bài này khác với việc đếm có chồng lấp (ví dụ trong aaaa với mẫu aa đáp số chồng lấp là $3$ nhưng không chồng lấp chỉ là $2$).