A palindrome of letters
Find the longest palindrome of letters in a text: a piece that reads the same from left to right and from right to left, ignoring spaces, punctuation, digits and line breaks. Case does not matter, and the Russian letters ё and е count as one letter. Letters are everything Unicode counts as a letter: Cyrillic, Latin and others.
Print it as it stands in the text: from the palindrome’s first letter to its last, with all the characters between them. If there are several longest, print the one that starts earlier.
The third test is 300,000 characters of War and Peace, the fourth Eugene Onegin, both in the original Russian.
Input
Text in UTF-8, one or more lines, 1 to 3 · 10⁵ characters in all; it has at least one letter. Lengths are counted in characters, not bytes.
Output
The first line holds the number of letters in the palindrome. The second, the piece of text itself, with every line break replaced by a space.
Examples
Example 1
А роза упала на лапу Азора!
21 А роза упала на лапу Азора
Example 2
Я иду с мечем, судия. — Гавриил Державин
15 Я иду с мечем, судия
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
First write out the letters in a row, bringing them to one form, and remember for each where it stands in the text. Then the problem is the longest palindrome in a string, and the piece of text is recovered from the places of the first and last letter.
2Hint 2
A palindrome has a centre, a letter or a gap. Expanding from each centre anew is expensive if there are many letters of one kind. Could the radius be taken ready-made from the mirror centre?
3The idea
Manacher’s algorithm. Put a separator that is not in the string between the letters: then palindromes of both parities have a centre that is a position, and the radius in the new string equals the length of the palindrome in letters. Inside the rightmost palindrome found, the radius of a centre is at least the radius of the reflected centre, cut down to the edge.
4Walkthrough
For position i with radius k the palindrome starts with letter (i − k) / 2 and contains k letters. Take the largest k, and on a tie the smaller start. Then, from the table of places, take the piece of text from the first letter to the last and replace line breaks with spaces. In Go the text has to be parsed into runes: Cyrillic letters take two bytes each.
4+Solution
5Complexity
O(n): writing out the letters is one pass, and Manacher makes fewer than 2m comparisons for a string with separators of length m.
6Common mistakes
- Expanding from each centre. This is
wrong.py. In the novel and the poem the palindromes are short, the longest in Onegin is seven letters, and it makes it in time. But in the fifth test almost all the letters are «а», with spaces and dashes between them, and every centre expands for thousands of steps. - Only odd ones. In the sixth test the longest palindrome has even length, 8000 letters.
- Ё and case. In the seventh test the longest is «Ёлка, вот ов, а клЕ»: without the rule “ё = е” and without converting to lower case it is not found.
- The piece without punctuation. The text has to be printed as it is, with punctuation, spaces and mixed case, not the written-out letters.