Xóa Ký Tự Trong Chuỗi

Cho chuỗi $S$ độ dài $N$ và chuỗi $T$ độ dài $M$. Hãy xóa số ký tự tối thiểu từ $S$ sao cho $T$ không xuất hiện là một xâu con liên tiếp trong chuỗi còn lại.

Dữ liệu vào

• Dòng 1: Chuỗi $S$ gồm các chữ cái thường
• Dòng 2: Chuỗi $T$ gồm các chữ cái thường

Dữ liệu ra

Số nguyên: số ký tự tối thiểu cần xóa.

Ràng buộc

• $1\le M\le N\le 10000$
• $M\le 1000$
• Tất cả ký tự là chữ cái thường (a-z)

Ví dụ