题目描述

贝西收集了 $N$ 颗石头，每颗石头上都有一个字母，贝西想把这些石头做成项链。

贝西的身边有另一只奶牛，这只奶牛的名字是一个长度为 $M$ 的字符串，贝西不希望这只牛的名字出现在她的项链上（项链的子串），她想知道，最少删掉几颗石头就可以避免这种情况发生。

输入格式

第一行：一个长度为 $N$ 的字符串，描述贝西的初始项链，每个字符的取值范围为 "a" 到 "z"。

第二行：一个长度为 $M$ 的字符串，表示另一只牛的名字，每个字符的取值范围为 "a" 到 "z"。

输出格式

输出一行，表示需要从贝西的项链中移除的最少石头数量，以确保项链中不包含另一牛的名字作为子串。

输入样例

ababaa 
aba

输出样例

1

数据范围

至少 $20\%$ 的测试点，$N \le 20$。 至少 $60\%$ 的测试点，$N \le 1000$，$M \le 100$。 对于所有测试点，$N \le 10000$，$M \le 1000$。 对于所有测试点，$M \le N$。

$\text{upd 2022.7.29}$：新增加一组 Hack 数据。