A22487.项链

母牛贝茜安排了一串N块石头，每块石头都包含一个字母表，她想把它们做成一条时尚的项链。

为了保护自己的财物，贝茜不想与目前住在谷仓一侧的另一头母牛分享她的项链。另一头牛的名字是一串 M 字符，Bessie 希望确保这根长度为 M 的绳子不会在代表她的项链的绳子的任何位置作为连续的子串出现（否则，另一头牛可能会误以为项链是给她的）。贝茜决定去掉项链上的一些石头，这样另一头牛的名字就不会以子绳的形式出现。请帮助贝茜确定她必须清除的最小岩石数量。

• 第 1 行：第一行是一条长度为 N 的字符串，描述了 Bessie 最初的项链;每个字符都在“a”到“z”的范围内。

• 第 2 行：第二行是谷仓中另一头奶牛的长度 M 名称，也由“a”到“z”的字符组成。

• 第 1 行：需要从 Bessie 的项链中移除的最小宝石数量，以便它不包含另一头牛的名字作为子字符串。

For at least 20% of test cases, N <= 20. 
For at least 60% of test cases, N <= 1000, M <= 100. 
For all test cases, N <= 10000, M <= 1000. 
For all test cases, M <= N.