Bessie đã xếp một chuỗi gồm \(N\) viên đá, mỗi viên mang một chữ cái duy nhất trong bảng chữ cái, và muốn kết chúng thành một chiếc vòng cổ thời trang.

Vì muốn bảo vệ đồ đạc của mình, Bessie không muốn chia sẻ chiếc vòng cổ với con bò khác đang sống cùng phía chuồng. Tên của con bò kia là một chuỗi gồm \(M\) ký tự, và Bessie muốn bảo đảm rằng chuỗi độ dài \(M\) này không xuất hiện dưới dạng một chuỗi con liên tiếp ở bất kỳ đâu trong chuỗi biểu diễn chiếc vòng cổ của cô (nếu không, con bò kia có thể nhầm tưởng chiếc vòng cổ dành cho mình). Bessie quyết định bỏ đi một số viên đá trên vòng cổ để tên của con bò kia không xuất hiện dưới dạng chuỗi con. Hãy giúp Bessie xác định số viên đá ít nhất mà cô phải bỏ đi.

Dữ liệu vào

• Dòng 1 chứa một chuỗi độ dài \(N\) mô tả chiếc vòng cổ ban đầu của Bessie; mỗi ký tự nằm trong khoảng từ a đến z.
• Dòng 2 chứa tên có độ dài \(M\) của con bò khác trong chuồng, cũng chỉ gồm các ký tự từ a đến z.

Phân nhóm

Trong ít nhất 20% số trường hợp kiểm thử, \(N \le 20\).

Trong ít nhất 60% số trường hợp kiểm thử, \(N \le 1000\) và \(M \le 100\).

Trong mọi trường hợp kiểm thử, \(N \le 10000\) và \(M \le 1000\).

Trong mọi trường hợp kiểm thử, \(M \le N\).

Dữ liệu ra

• Dòng 1 chứa số viên đá ít nhất cần bỏ khỏi chiếc vòng cổ của Bessie để nó không chứa tên của con bò kia dưới dạng chuỗi con.

Ví dụ

ababaa
aba

1

Nguồn

USACO 2013 March Contest, Gold — Problem 3: Necklace

Tác giả đề: Yan Gu, 2013.