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

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

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

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

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

USACO