0088. Two Strings

Input file name:	2strings.in
Output file name:	2strings.out
Time limit:	2 s
Memory limit:	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.in	2strings.out
1 toolkit kitten	10 toolkitten

Source: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Discuss       Submit a solution



Printable version