05/12/2025 14:59:16

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

250. Две строки

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вам заданы две строки длиной не более 10000 символов. Назовем строку хорошей, если она удовлетворяет условию, что если дописать ее в конец самой себе достаточно много раз, то в полученной строке будут содержаться в качестве подстрок обе заданные строки.

Например, для строк "ababa" и "bab" строка "ab" является хорошей – действительно, дописав ее в конец себе два раза, мы получим строку "ababab", которая содержит обе заданные строки в качестве подстрок.

Для двух заданных строк найдите самую короткую хорошую строку.

Первая строка ввода содержит целое число `N` (1 ≤ N ≤ 100) — количество тестов. Каждый тестовый случай состоит из двух строк длиной не более 10000, содержащих символы с ASCII-кодами от 33 до 127.

Выведите для каждого тестового случая сначала минимальную длину хорошей строки, а на следующей строке – получившуюся строку. Если существует несколько различных оптимальных хороших строк, то выведите любую.

Пример ввода

1
kitten
toolkit

Пример вывода

10
toolkitten

Источник: http://neerc.ifmo.ru/school/archive/

02/07/2007	Лето 2007 дорешивание ( 8E)
18/07/2007	Лето 2007 - 8 (E)
16/05/2009	Занятие 18 (E)
19/05/2012	Занятие 19 (A)
15/07/2020	Летние сборы - 8 (A)
05/05/2025	ЦОП2: КМП (проводит BOGAT) (B)