Task C Gold USACO March

Problem 3: Necklace [Yan Gu, 2013]

Беси выложила N камней, на каждом одна буква алфавита и хочет
построить ожерелье.

Имя соседки Беси представляет строку из M символов.
Беси хочет, чтобы эта строка из M символов не встречалась как непрерывная
подстрока в строке, представляющей ее ожерелье.

Беси решила удалить некоторые из камней из своего ожерелья, так чтобы
имя другой коровы не встречалась как подстрока.

Определите минимальное количество камней, которое она должна удалить.

PROBLEM NAME: necklace

INPUT FORMAT:

* Строка 1: Строка длины N, описывающая ожерелье Беси
            все символы в диапазоне a-z.

* Строка 2: Строка длины M, описывающая имя другой коровы
            все символы в диапазоне a-z.

SAMPLE INPUT (файл necklace.in):

ababaa
aba

INPUT DETAILS:

Для 20% тестов, N <= 20.
Для 60% тестов, N <= 1000, M <= 100.
Для всех тестов, N <= 10000, M <= 1000.
Для всех тестов, M <= N.

OUTPUT FORMAT:

* Строка 1: Минимальное количество камней, которое нужно удалить
            из ожерелья Беси, чтобы оно не содержало имя другой
            коровы как подстроку

SAMPLE OUTPUT (файл necklace.out):

1

OUTPUT DETAILS:

Модифицированная строка должна быть "abbaa".