EDIT2 - Editor Inverse

You are given a text. Calculate the minimum number of keystrokes needed to produce this text, if the editor described below is used.
If you haven't read the problem "Editor" before, here is a description of the functionality of the editor:

  • '\n': begin a new line. If the last line was empty, stop processing and print out all lines.
  • 'd': copy all characters from the current line, and append them after the last character in this line. For example, if current line contains ab, and d is pressed two times, the result will be abababab
  • any other character: append it to the current line.

Input

The input consists of exactly ten test cases. Each test case consists of a line with at most 600 characters. The character 'd' is not used in any of the lines, but all other printable ascii characters may occur.

Output

For each test case, first print a line containing the minimum number of key strokes to produce the given line of text. In the next lines, write the keys that are pressed to produce the text. If there are several possibilities with minimum number of keystrokes, you should also minimise the number of lines, if there is still more than one possibility, minimise number of keystrokes before the first '\n', then second '\n', ...

Since 'd' is a costly operation in the editor, for each output line you should minimise the number of 'd' characters as the 2nd criterion after minimising number of keystrokes in this line.

The original input line should be the same as the output of the editor (processing the output you produce), if '\n' characters are ignored.

Notice that you have to terminate the input for the editor with two '\n'.

Example

Here only two test cases.

Input:
00001123444456789
000011234444446789 Output: 18 00d1123444456789 18 00d1123 444d6789

Added by:Adrian Kuegel
Date:2004-06-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:own problem

hide comments
2009-06-17 09:54:30 Eigenray
Use gets( ) instead of scanf("%s", ).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.