0088. Two Strings

Имя входного файла: 2strings.in
Имя выходного файла: 2strings.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

You are given two strings. Your task is to find the string with the minimal possible length which being infinitely appended to itself will contain two given strings.

Input file

First line contains the number of test cases (up to one hundred). Each test case consists of two strings with no more than 10000 characters each. All characters have ASCII code from 33 to 126.

Output file

For each test case output two lines. First line must contain the number of characters in the shortest possible string which will contain two given substrings if it is looped repeatedly. The next line must contain one of such shortest strings.

Separate output for different test cases with a single blank line.

Examples:

2strings.in2strings.out
1 toolkit kitten10 toolkitten


Источник: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Обсудить       Отправить решение



Версия для печати