| Author: | M. Sporyshev, A. Klenin, A. Baranov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
For arbitrary non-empty strings S1 and S2, the Fibonacci sequence of strings is defined by a recurrence Si + 2 = Si + 1 + Si, where the '+' sign denotes string concatenation.
Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains Sn = T. Note that any string of length 2 or more has Fibonacci level 3.
Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S1 and S2 of corresponding Fibonacci sequence of strings.
Input file contains a single string T, consisting of lowercase Latin letters.
Output file must contain 3 lines: integer n followed by strings S1 and S2.
If there are several optimal solutions, output any of them.
2 ≤ |T| ≤ 106
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|