Having heard that you are busy with a project (something about keeping track of time when travelling), your mischevious friends thought that it might be funny to constantly send you text messages in order to distract you. However, you can write a program to retaliate this lame plan and send a copy of their messages right back! Always playing a one-up, you are also going to repeat every message twice.
While writing the program, you notice that certain words don't have to be repeated twice completely to still contain two copies of it in the message. For example, the word "amalgam" can be written as "amalgamalgam", since it still contains two copies of the word, while saving 2 characters.
Give a word, determine what your program should output if it is to save characters in this fashion. The trivial solution of merging the entire word doesn't count though; that is, the input of easy results in easyeasy. The input of oo results in ooo which is the shortest overlap without turning into the previously mentioned trivial case.
The input file DATA2.txt will contain 5 test cases. Each case is a line with a single string S with 1 <= length(S) <= 256, all lowercase letters, possibly containing spaces.
The output file OUT2.txt will contain 5 lines of output. Each line is a repeated (but condensed where possible) copy of the input phrase.
amalgam rotor easy case a oo
amalgamalgam rotorotor easy caseasy case aa ooo