Palindromes: borrow from the mirror

Level, noon, racecar: a palindrome reads the same forwards and backwards. Checking whether a whole word is one is easy: compare its two ends and step inwards, the two pointers pattern. The harder question is finding the longest palindrome inside a string. In “bananas” it is “anana”.

The obvious way checks every substring. A string of n letters has n(n + 1)/2 of them, and checking one can take up to n/2 comparisons, so the search is O(n³). On 1,000 letters that is 500,500 substrings, and if the letters are all a's, every check runs to the middle: about 83 million comparisons.

This lesson cuts that twice. Growing each palindrome from its middle is O(n²). Manacher's algorithm is O(n): like KMP in string matching, it never pays twice for what it has already proved, and here the proof is a mirror.

palindrome and substring

A substring is a run of consecutive letters; it is a palindrome when it reads the same both ways.

centre

The middle of a palindrome: a letter when its length is odd (the c of “abcba”), the gap between two letters when it is even (between the b's of “abba”). n letters have 2n − 1 centres.

radius

How far a palindrome reaches out from its centre. Manacher records P[i], the radius of the longest palindrome centred at cell i.

separators

The string T puts # between and around the letters, so “aba” becomes #a#b#a#: 2n + 1 cells, and every centre, letter or gap, is a cell of its own.

C, R and the mirror

C is the centre of the palindrome found so far that reaches furthest right, and R the cell where it ends. The mirror of cell i is 2C − i, its reflection in C.

A palindrome is symmetric about its centre, so grow it from there: put two pointers on the centre and step them outwards while the letters under them match. They stop just outside the longest palindrome with that centre. Try every centre and keep the longest.

There are 2n − 1 centres, and one can grow for about n/2 steps, so this is O(n²). On ordinary text most centres stop after a comparison or two, and it needs no extra memory: the usual interview answer. On aaaa…a nothing stops early: every centre grows until it meets an end of the string, about 500,000 comparisons for 1,000 a's. A dynamic programming table, where s[i..j] is a palindrome when its ends match and s[i + 1..j − 1] is one, is O(n²) too, with O(n²) memory.

Manacher's algorithm makes two changes. First, it works on T, with # between and around the letters. A gap is now a cell, so one loop over T's 2n + 1 cells tries every centre, odd and even. And the longest palindrome around any cell starts and ends on a #, so a radius of p holds exactly p letters of s: P[i] is simply its length.

Second, it remembers the palindrome found so far that reaches furthest right: centred at C, ending at R. Take a centre i after C but before R. Its mirror, 2C − i, lies the same distance left of C, and the big palindrome makes the letters around i the reverse of those around the mirror. A palindrome reversed is the same palindrome, so the mirror's palindrome is around i too, at least as far as the big one reaches. The mirror's radius is already known, so i starts from min(R − i, P[2C − i]) instead of 0.

Now “abababc”. Before each centre inside the rightmost palindrome, the run asks what radius it starts from, and after each palindrome is written, whether R moves. Watch for a mirror whose palindrome is longer than the room left before R.

Here is expanding around all 2n − 1 centres in one loop. An even centre is the letter at index centre / 2, so lo and hi both start on it; an odd one is the gap after the letter at (centre − 1) / 2, so they start on the letters either side. When the while loop stops, they sit one place outside the palindrome, so its length is hi − lo − 1. The program finds the longest palindrome in “see”.

def longest_palindrome(s):
    best = ''
    for centre in range(2 * len(s) - 1):
        lo = centre // 2
        hi = lo + centre % 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > len(best):
            best = s[lo + 1:hi]
    return best

print(longest_palindrome('see'))

Forgetting the gaps is the classic bug here.

Manacher's start, min(R − i, P[2C − i]), comes in three cases, and in two of them it is already the final radius:

• The mirror's palindrome ends inside the big one: i's is exactly as long, and its next comparison is bound to fail. In “abacaba”, cell 9 copied radius 1 from cell 5, and c against b failed.
• It sticks out past the big one's left edge: only R − i is mirrored, and that is exactly the radius, or the palindrome around C would reach further too. In the challenge, cell 9's mirror, cell 5, had radius 5, but R − i was 3, so P[9] = 3.
• It ends exactly at the edge: nothing past R has been compared, so comparing carries on. In the challenge, cell 7 borrowed 3 from cell 3 and grew to 5.

The visualiser still makes the comparison that is bound to fail, and says so; a tuned version skips it.

So a comparison can only match past R, and each match pushes R right for good. One repeated letter, the slowest input for expanding from zero, shows it best.

• A palindrome is symmetric about its centre: a letter for odd length, a gap for even. n letters have 2n − 1 centres; skip the gaps and every even-length palindrome is missed.
• Checking every substring is O(n³). Expanding from each centre is O(n²) at worst (aaaa…a), fast on ordinary text and O(1) in memory: the usual interview answer.
• Manacher puts # between and around the letters, so every centre is a cell and P[i] is the palindrome's length in s.
• It keeps C and R, the palindrome reaching furthest right. A centre i before R starts from min(R − i, P[2C − i]), which is final unless the mirror's palindrome ends exactly at the edge.
• Every match pushes R right for good, and each centre has at most one mismatch: under 2|T| comparisons, O(n).
• Next: practise with Longest Palindromic Substring, where expanding around centres is plenty, and Palindrome, Ignoring Punctuation, two pointers moving inwards. Or try your own words on Manacher's visualiser.