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

Палиндромный контест

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

C. Не общие подпалиндромы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вам даны строки A и B.
Ваша задача — найти 3 числа:
1. x = количество непустых палиндромов p таких, что f(A, p) > f(B, p);
2. y = количество непустых палиндромов p таких, что f(A, p) = f(B, p) и f(A, p) ≠ 0;
3. z = количество непустых палиндромов p таких, что f(A, p) < f(B, p),
где f(A, p) = количество вхождений p в A.

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

Первая строка содержит число тестов T. Следующие 2T строки содержат непустые строки A и B для каждого теста. Длины A и B не превосходят 200 000. Гарантируется, что размер входных данных не превышает 8 мегабайт.

Результат

Для каждого теста i выведите «Case #i: x y z» в отдельной строке.

Пример

исходные данныерезультат
3
abacab
abccab
faultydogeuniversity
hasnopalindromeatall
abbacabbaccab
youmayexpectedstrongsamplesbutnow
Case #1: 4 1 2
Case #2: 8 3 9
Case #3: 13 0 15
Автор задачи: Михаил Рубинчик
Источник задачи: Палиндромный контест, 11 июля 2015
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2059. Не общие подпалиндромы