Задача Regexp
У вас є деякий текст S - послідовність маленьких літер латинського алфавіту. Вам необхідно знайти у цьому тексті кількість підрядків, які відповідають патерну, тобто шаблону.
Патерни у нас бувають лише вигляду “A*B” (замість A і B мають бути задані маленькі символи латиниці). Цей патерн означає наступне:
- рядок починається з символу A і закінчується символом B;
- довжина підрядка, що відповідає паттерну, не враховуючи А і В, ділиться націло на K.
Наприклад, якщо маємо патерн e*s та k=2, то рядки “es”, “eggs”, “errors”, “ends” підходять під цей патерн, а ось рядки “elixirs”, “posix” або “regexp” - не підходять.
Технічні умови
Програма Regexp читає з стандартного пристрою введення (клавіатури) рядок S - заданий текст, що складається лише з малих символів латиниці, довжина якого не перевищує 100 000. З наступного рядка програма має зчитати патерн – рівно три символи, У останньому рядку міститься єдине натуральне число К, що не перевищує 100 000.
Програма виводить на стандартний пристрій виведення (екран) єдине число – шукану величину.
Приклади
|
Введення |
Виведення |
|
abacaba a*a 1 |
6 |
|
ofoofooof o*f 3 |
4 |