A2776. 项链
编程题
提高+/省选-
知识点
题目描述
母牛贝茜安排了一串N块石头，每块石头都包含一个字母表，她想把它们做成一条时尚的项链。
为了保护自己的财物，贝茜不想与目前住在谷仓一侧的另一头母牛分享她的项链。另一头牛的名字是一串 M 字符，Bessie 希望确保这根长度为 M 的绳子不会在代表她的项链的绳子的任何位置作为连续的子串出现（否则，另一头牛可能会误以为项链是给她的）。贝茜决定去掉项链上的一些石头，这样另一头牛的名字就不会以子绳的形式出现。请帮助贝茜确定她必须清除的最小岩石数量。
为了保护自己的财物，贝茜不想与目前住在谷仓一侧的另一头母牛分享她的项链。另一头牛的名字是一串 M 字符，Bessie 希望确保这根长度为 M 的绳子不会在代表她的项链的绳子的任何位置作为连续的子串出现（否则，另一头牛可能会误以为项链是给她的）。贝茜决定去掉项链上的一些石头，这样另一头牛的名字就不会以子绳的形式出现。请帮助贝茜确定她必须清除的最小岩石数量。
输入格式
* 第 1 行：第一行是一条长度为 N 的字符串，描述了 Bessie 最初的项链;每个字符都在“a”到“z”的范围内。
* 第 2 行：第二行是谷仓中另一头奶牛的长度 M 名称，也由“a”到“z”的字符组成。
* 第 2 行：第二行是谷仓中另一头奶牛的长度 M 名称，也由“a”到“z”的字符组成。
输出格式
* 第 1 行：需要从 Bessie 的项链中移除的最小宝石数量，以便它不包含另一头牛的名字作为子字符串。
输入输出样例
输入 #1
ababaa aba
输出 #1
1
说明/提示
```cpp
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.
```
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.
```