Necklace

Bessie the cow has laid out a row of $N$ rocks, each painted with a single lowercase letter, to build into a fashionable necklace. Reading the rocks in order gives a string of length $N$.

Being protective of her belongings, Bessie does not want to share her necklace with the other cow living on her side of the barn. That cow's name is a string of $M$ characters, and Bessie wants to be sure this length-$M$ string never appears as a contiguous substring of her necklace (otherwise the other cow might mistakenly think the necklace is hers). Bessie decides to remove some rocks so that the other cow's name does not appear as a substring. (When rocks are removed, the remaining rocks keep their original order and join into the new necklace string.)

Determine the minimum number of rocks Bessie must remove.

• Line 1: a string of length $N$ describing Bessie's initial necklace; each character is between a and z.
• Line 2: the length-$M$ name of the other cow in the barn, also made of characters from a to z.

• Line 1: the minimum number of rocks that must be removed from Bessie's necklace so that it does not contain the other cow's name as a substring.

• $1 \le M \le N \le 10000$
• $M \le 1000$
• Every character of the necklace and the name is a lowercase letter from a to z.