Description

Bessie the cow will string together $N$ lettered gems to make a fashionable necklace.

Bessie takes good care of her belongings and does not want to share this necklace with another cow currently living on the other side of the barn. That cow’s name is a string of length $M$, and Bessie needs to ensure that this length-$M$ string does not appear as a contiguous substring anywhere in her necklace string (otherwise that cow might mistakenly think the necklace is for her). Bessie decides to remove some gems from the necklace to ensure the other cow’s name does not appear as a substring. Please help Bessie determine the minimum number of gems that must be removed.

Input Format

Line 1: A string of length $N$ describing Bessie’s initial necklace; each character is in the range a to z.

Line 2: A string of length $M$ describing the other cow’s name in the barn, also consisting of characters a to z.

Output Format

Line 1: The minimum number of gems to remove from Bessie’s necklace so that it no longer contains the other cow’s name as a substring.

ababaa 
aba 

1 

Hint

At least 20% of the test cases have $N \le 20$.

At least 60% of the test cases have $N \le 1000, M \le 100$.

For all test cases, $N \le 10000, M \le 1000$.

For all test cases, $M \le N$.

Sample explanation: The modified necklace should be abbaa.

Updated on $\text{2022.7.29}$: An additional set of hack testdata was added.

The Chinese statement for this problem was provided by ChampionCyan.

Translated by ChatGPT 5