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

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

Ограничение времени: 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