ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрФУ 2012

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Страшное марсианское слово

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У жителей разных планет разные суеверия. Марсиане смеются над землянами, страдающими трискаидекафобией и гексакосиойгексеконтагексафобией. А земляне подшучивают над тем, что в марсианском языке есть страшное слово. Марсиане боятся не только этого страшного слова, но и всех слов, которые получаются перестановкой букв страшного слова.
В марсианском алфавите 729 000 букв. Журналист Овчинников, живущий на Марсе и изучающий язык марсиан, записывает буквы марсианского алфавита тройками символов с ASCII кодами от 33 до 122. Недавно он написал книгу о быте и культуре марсиан. Перед тем как отправить книгу в печать, Овчинников хочет посчитать количество подстрок в тексте книги, которые напугают марсиан.

Исходные данные

В первой строке записано страшное марсианское слово, состоящее не более чем из 8 000 марсианских букв. Во второй строке приводится текст книги Овчинникова, длина которого не превосходит 500 000 марсианских букв. И в страшном слове, и в тексте книги есть хотя бы одна буква. Каждая марсианская буква записана тройкой символов с ASCII кодами от 33 до 122, соседние буквы разделены пробелом.

Результат

Выведите количество подстрок в тексте книги журналиста Овчинникова, являющихся страшными для марсиан.

Пример

исходные данныерезультат
aaa bbb ccc
aaa aaa bbb ccc aaa zzz aaa bbb ccc
3

Замечания

Страшными для марсиан являются две подстроки «aaa bbb ccc» (начинающиеся со второй и с седьмой позиции в тексте) и подстрока «bbb ccc aaa».
Автор задачи: Андрей Демидов (подготовка — Алексей Самсонов)
Источник задачи: Открытое личное первенство УрФУ по программированию 2012
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1941. Страшное марсианское слово