Manacher’s palin­dromes

ARRS-6 checked whether one string is a palindrome with two pointers. Finding every palindrome inside a string looks like O(n²) work, because there can be that many. Manacher’s method (1975) finds them all, described by one number per centre, in O(n), using the fact that a palindrome is its own mirror image.

Palindromes around a centre

Every palindrome has a centre. A palindrome of odd length, like "aba", is centred on a letter. One of even length, like "abba", is centred on the gap between two letters. If a palindrome is centred at some point, removing its first and last letters leaves a shorter palindrome with the same centre. So the palindromes around one centre are nested, and one number describes them all:

• d₁[i]: how many odd-length palindromes are centred on letter i. The longest is s[i − d₁[i] + 1 .. i + d₁[i] − 1], with 2·d₁[i] − 1 letters.
• d₂[i]: how many even-length palindromes are centred on the gap just before letter i. The longest is s[i − d₂[i] .. i + d₂[i] − 1], with 2·d₂[i] letters.

The simple way grows each palindrome from its centre, one pair of letters at a time, until the pair differs or the string ends. There are 2n − 1 centres. On ordinary text each one stops quickly, but on "aaaa…" the centre in the middle grows n/2 times, and the total is about n²/4 comparisons: 2.5 billion for 100,000 letters.

The mirror rule

Manacher’s method goes through the centres from left to right and keeps the box [l, r]: of the palindromes found so far, the one whose right end r is furthest right.

Take a centre i inside the box. The box is a palindrome, so reading it from the right gives the same letters as reading from the left: the letter at l + t equals the letter at r − t. Centre i has a mirror centre j = l + r − i on the other side of the box’s middle, and d₁[j] is already known. Every palindrome around j that lies inside the box has a mirror image around i, of the same length.

• j’s longest palindrome ends inside the box (d₁[j] < r − i + 1): just outside it on both sides are two letters that differ, and both are inside the box. Their mirror images are the two letters just outside the palindrome around i, so they differ too. Then d₁[i] = d₁[j], with no comparisons.
• Otherwise: the mirror gives the palindrome around i up to the box’s right end, d₁[i] ≥ r − i + 1, but nothing is known past r. Compare from there.

For a centre outside the box, grow from the centre as the simple way does. When a palindrome reaches past r, it becomes the box.

# one centre i, with the box [l, r] from the centres before it
k = 1 if i > r else min(d1[l + r - i], r - i + 1)   # the mirror rule
while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
    k += 1                          # grow past what the box gives
d1[i] = k
if i + k - 1 > r:                   # reaches further right
    l, r = i - k + 1, i + k - 1

Step through the figure. In "abacabad", the palindrome "abacaba" around place 3 becomes the box, and places 4, 5 and 6 read their answers from places 2, 1 and 0.

Why it is O(n)

The same count as for the Z-algorithm (lesson 3). A comparison inside the while loop either fails, at most once per centre, or succeeds. A successful comparison at centre i looks at the letter i + k, which is past r: the mirror rule already covered everything up to r. After the loop, r moves at least that far. r never moves left and stays below n, so there are at most n successful comparisons in all, and the method costs O(n) time and O(n) memory.

Even lengths, and one array for both

Even lengths work the same way, centred on the gap before each place i.

Three things change: k starts at 0 outside the box, the mirror of the gap before i is the gap before l + r - i + 1, and the letters compared are s[i - k - 1] and s[i + k]. A palindrome then reaches from i - k to i + k - 1, which is the new box when it goes past r. STRG-P6 needs both kinds, and the two sums below.

A common shortcut avoids the second function. Put a character that is not in s between every two letters and at both ends: "abba" becomes "#a#b#b#a#". Now every palindrome of s, odd or even, is an odd palindrome of the new string centred on a letter or on a #, and one run of the odd-length method finds them all. In the new string, d₁[i] − 1 is the length of the longest palindrome of s with that centre.

What the radii give you

• The longest palindrome: the largest 2·d₁[i] − 1 or 2·d₂[i], read off in one pass.
• How many palindromes, counted by position: sum(d₁) + sum(d₂). In "aaa" that is (1 + 2 + 1) + (0 + 1 + 1) = 6: three of length 1, two of length 2, one of length 3. The count can be close to n²/2, but it is found in O(n).
• Is s[a..b] a palindrome? Look at its centre: it is one exactly when the palindrome around that centre reaches a. Each question then costs O(1).
• The shortest palindrome made by adding letters to the front: find the longest palindrome that starts at place 0. Either Manacher’s array or KMP’s table of s + "#" + s[::-1] gives it.

Now try STRG-P6, Palindromes in a string.