Беси выложила N камней, на каждом одна буква алфавита и хочет построить ожерелье.
Имя соседки Беси представляет строку из M символов. Беси хочет, чтобы эта строка из M символов не встречалась как непрерывная подстрока в строке, представляющей ее ожерелье.
Беси решила удалить некоторые из камней из своего ожерелья, так чтобы имя другой коровы не встречалась как подстрока.
Определите минимальное количество камней, которое она должна удалить.
PROBLEM NAME: necklace
Формат входных данных
* Строка 1: Строка длины N, описывающая ожерелье Беси все символы в диапазоне a-z.
* Строка 2: Строка длины M, описывающая имя другой коровы все символы в диапазоне a-z.
Формат выходных данных
* Строка 1: Минимальное количество камней, которое нужно удалить из ожерелья Беси, чтобы оно не содержало имя другой коровы как подстроку
Примечание
Модифицированная строка должна быть "abbaa".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ababaa
aba
|
1
|