Necklace Name Avoidance

Bessie the cow has collected a necklace made of N rocks, with each rock containing a letter. She wishes to ensure that the cow's name, a string of M characters, does not appear as a contiguous substring in the necklace. To achieve this, Bessie may remove some rocks from the necklace.

Your task is to determine the minimum number of rocks to remove so that the cow's name never appears as a substring in the remaining necklace. Note that when a rock is removed, the order of the remaining rocks is preserved.

The solution may involve dynamic programming together with pattern matching (for instance, using a KMP automaton) to efficiently prevent the occurrence of the forbidden substring.

inputFormat

The input consists of two lines:

• The first line contains the necklace string, consisting of English letters.
• The second line contains the cow's name string (the forbidden substring).

outputFormat

Output a single integer representing the minimum number of rocks that must be removed so that the cow's name does not occur as a contiguous substring in the necklace.

sample

abcde
cd

1