P3082 [USACO13MAR] Necklace G

奶牛贝茜将串起 $N$ 颗刻有字母的宝石，打算制作一条时尚项链。 贝茜对自己的物品很爱惜，她不想与目前住在谷仓另一侧的另一头牛分享这条项链。那头牛的名字是一个长度为 $M$ 的字符串，贝茜需要确保这个长度为 $M$ 的字符串不会作为连续子字符串出现在她项链字符串的任何位置（否则那头牛可能会误以为这条项链是给她的）。贝茜决定移除项链中部分石头，以确保另一头奶牛的名字不会作为子串出现。请帮助贝茜确定必须移除的最小石头数量。

第 $1$ 行：描述贝茜初始项链的长度为 $N$ 的字符串；每个字符在 `a` 到 `z` 范围内。 第 $2$ 行：描述牛棚中另一头奶牛的长度为 $M$ 的名字，同样由 `a` 到 `z` 的字符组成。

第 $1$ 行：从贝茜项链中移除最少数量的宝石，使其不再包含另一头奶牛名字的子串。

至少 $20\%$ 的测试用例中，$N\le 20$。 至少 $60\%$ 的测试用例中，$N\le 1000，M\le 100$。 所有测试用例中，$N\le 10000，M\le 1000$。 所有测试用例中，$M\le N$。 样例解释：修改后的项链应为 `abbaa`。 --- 更新于 $\text{2022.7.29}$：新增一组 Hack 数据。 本题中文题面由 [ChampionCyan](https://www.luogu.com.cn/user/1036180) 提供。