题目描述

奶牛贝茜将串起 $N$ 颗刻有字母的宝石，打算制作一条时尚项链。

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

输入格式

第 $1$ 行：描述贝西初始项链的长度为 $N$ 的字符串；每个字符在 a 到 z 范围内。

第 $2$ 行：描述牛棚中另一头奶牛的长度为 $M$ 的名字，同样由 a 到 z 的字符组成。

输出格式

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

ababaa 
aba 

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 提供。