Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
250. Две строки
Поиск подстроки, префикс-функция, z-функцияОлимпиадные задачи на русском языке
| 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) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вам заданы две строки длиной не более 10000 символов. Назовем строку хорошей, если она удовлетворяет условию, что если дописать ее в конец самой себе достаточно много раз, то в полученной строке будут содержаться в качестве подстрок обе заданные строки.
Например, для строк "ababa" и "bab" строка "ab" является хорошей – действительно, дописав ее в конец себе два раза, мы получим строку "ababab", которая содержит обе заданные строки в качестве подстрок.
Для двух заданных строк найдите самую короткую хорошую строку.
Первая строка ввода содержит целое число `N` (1 ≤ N ≤ 100) — количество тестов. Каждый тестовый случай состоит из двух строк длиной не более 10000, содержащих символы с ASCII-кодами от 33 до 127.
Выведите для каждого тестового случая сначала минимальную длину хорошей строки, а на следующей строке – получившуюся строку. Если существует несколько различных оптимальных хороших строк, то выведите любую.
Пример ввода
1 kitten toolkit
Пример вывода
10 toolkitten
