LSQF - Longest Square Factor
Given a string x, the string obtained by concatenating x to itself is sometimes called the square of x.
Given a string s, output the longest string x such that its square is a substring of s. If you find more than one solution, output the lexicographically smallest.
Input
The first and only line of input contains a string s (consisting only of lowercase letters of the english alphabet). The length of s is less than or equal to 105.
Output
To the first line of output print the length of the string x.
To the second line print the string x.
Such a string will always exist in the test data.
Example
Input: abcabc
Output: 3
abc
hide comments
Shaka Shadows:
2011-08-22 15:30:39
Really nice problem!!! Thanks Gustav :) |
|
gustav:
2011-08-22 15:30:39
Seems fine now :D |
|
Oleg:
2011-08-22 15:30:39
Nice try |
|
gustav:
2011-08-22 15:30:39
You asked for it :) |
|
Oleg:
2011-08-22 15:30:39
Try again :) |
|
gustav:
2011-08-22 15:30:39
Ok, so just a little note here: I might throw in a few new test cases every now and then so if your solution isn't correct - your AC won't last forever :) Last edit: 2011-03-15 15:48:27 |
Added by: | gustav |
Date: | 2011-03-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |