ManacherLongest palindrome

01Why it exists

Reach for it when you see:Longest palindromic substring, number of palindromic substrings, how far a palindrome extends from each position, many range palindrome queries, reverse-complement stretches of DNA, needing something faster than O(n²) centre expansion.

02The core idea

The most direct way to find the longest palindromic substring is centre expansion: take every character, and every gap between two characters, as a centre and push outward until the two sides differ. On aaaa…a every centre expands all the way, so the worst case is O(n²). Odd-length palindromes are centred on a character and even-length ones on a gap, and handling the two cases separately is a nuisance, so the first move is to insert a separator between every pair of characters and at both ends: s = abaaba becomes T = #a#b#a#a#b#a#, of length 2n + 1, and now every palindrome's centre is some position of T. p[i] is the radius of the palindrome centred at i in T, and conveniently that radius is exactly the corresponding palindrome's length in s, starting at (i − p[i]) / 2.

Manacher keeps track of the palindrome that reaches furthest right: its centre c and its right edge r = c + p[c]. When it gets to i, if i < r then i lies inside that big palindrome and its mirror about c, j = 2c − i, has already been computed. The big palindrome is symmetric, so the characters around i are the mirror image of the characters around j. If p[j] < r − i, then j's palindrome — along with the character that stopped it — lies entirely inside the big one, so i stops at the matching place and p[i] = p[j] outright, with no comparisons at all. If p[j] ≥ r − i, all that is guaranteed is a radius of at least r − i, because nothing beyond the right edge has been looked at yet, so expansion continues from there. And if i lies outside the right edge, expansion starts from radius 0. After each expansion, if i + p[i] > r, the centre and right edge move to i.

Complexity: when expansion starts from min(p[j], r − i), every successful comparison pushes the right edge one slot further right, and r only ever grows, up to 2n + 1 — so the successful comparisons total O(n). Failed comparisons are at most one per i. That makes the whole thing O(n) time and O(n) space. The single p array it produces answers a lot of questions: the largest p[i] is the longest palindrome; there are ⌈p[i] / 2⌉ palindromes centred at i, and summing that over all centres gives the total number of palindromic substrings; and s[l..r] is a palindrome exactly when p[l + r + 1] ≥ r − l + 1.

Common traps: skipping the separators leaves you finding only odd-length palindromes, so abba is missed; the index conversion between T and s is off by one, and the start has to be (i − p[i]) / 2; forgetting to take the minimum with r − i when copying the mirror radius treats unseen characters beyond the right edge as if they were symmetric; and expansion that does not bounds-check both ends. When p[j] is strictly greater than r − i the answer really is r − i, but writing the code to keep expanding regardless costs only one extra failed comparison. How this relates to the neighbouring lessons: it is the same trick as the previous lesson, the Z-Algorithm — borrow the answer from a mirror position inside the furthest-reaching interval, and only compare by hand once you go past that interval. String hashing plus a binary search on the radius also gets you O(n log n), and the palindrome table built by interval DP is O(n²), which Manacher can replace whenever only the palindrome information is needed.

03The algorithm

1. 1Insert a separator between every pair of characters in s and at both ends, giving a T of length 2n + 1. Set every entry of p to 0 and c = r = 0.
2. 2For each i: if i < r, set p[i] = min(p[2c − i], r − i); otherwise set p[i] = 0.
3. 3While neither end runs off the string and T[i − p[i] − 1] = T[i + p[i] + 1], increment p[i].
4. 4If i + p[i] > r, set c = i and r = i + p[i].
5. 5Read off the answers: the largest p[i] is the longest palindrome's length, starting at (i − p[i]) / 2 in s; and s[l..r] is a palindrome exactly when p[l + r + 1] ≥ r − l + 1.

04Interactive demo

s = abaaba becomes T = #a#b#a#a#b#a# once the # separators go in, 13 characters long. In the first row blue is i, green is its mirror 2c − i about the current centre, and yellow is the palindrome that grows out from i; the second row marks the palindrome that reaches furthest right. i = 1 and i = 3 both sit outside the right edge and have to expand honestly, and i = 3 — centred on b — reaches radius 3, that is aba, pushing the right edge out to 6. The mirror of i = 4 is 2, and p[2] = 0 is smaller than the 2 slots left to the right edge, so the 0 is copied straight over. i = 6 is the # between the two a's; its mirror gives p[0] = 0, which equals the 0 slots left to the right edge, so it has to expand on its own — all the way to both ends of T, radius 6, pushing the right edge to 12. After that i = 7, 8 and 10 all copy their mirrors, while at i = 9, 11 and 12 the mirror radius exactly reaches the right edge, but since the right edge is already the end of the string they stop after one comparison. The largest p is at i = 6, which corresponds to abaaba: length 6, starting at 0 in s.

05Code

Python uses None as the separator, which is guaranteed to equal no character, and demonstrates the longest palindrome, the palindromic substring count, and O(1) range palindrome queries. C++ pulls "do these two symmetric positions agree?" out into a parameter, so one Manacher finds both ordinary palindromes and complementary palindromes in DNA. A position that does not match itself cannot be a centre — a line that changes nothing for ordinary palindromes, but which rules out spurious base-centred palindromes in DNA. The two stretches the example turns up are precisely the EcoRI and BamHI cut sites.

def manacher(s):
    """Palindrome radii p over t = #s[0]#s[1]#…#. p[i] is exactly the palindrome's length in s. O(n)"""
    t = [None] * (2 * len(s) + 1)
    t[1::2] = s                                 # characters at odd positions, separators at even ones (None equals no character)
    n = len(t)
    p = [0] * n
    c = r = 0                                   # the palindrome reaching furthest right: centre c, right edge r = c + p[c]
    for i in range(n):
        if i < r:
            p[i] = min(p[2 * c - i], r - i)     # copy the mirror's radius, but borrow no further than the right edge
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1                           # past the right edge there is nothing to copy, so compare outward
        if i + p[i] > r:
            c, r = i, i + p[i]
    return p


def longest_palindrome(s):
    p = manacher(s)
    i = max(range(len(p)), key=p.__getitem__)
    start = (i - p[i]) // 2                     # convert a position in t back to a position in s
    return s[start:start + p[i]]


def count_palindromes(s):
    """Palindromic substrings in total (different positions count separately): each centre gives ceil(p / 2)"""
    return sum((v + 1) // 2 for v in manacher(s))


class PalindromeQuery:
    """O(n) preprocessing, then every 'is s[l..r] a palindrome?' question is O(1)"""

    def __init__(self, s):
        self.p = manacher(s)

    def is_palindrome(self, l, r):              # closed interval [l, r]; its centre in t is l + r + 1
        return self.p[l + r + 1] >= r - l + 1


if __name__ == "__main__":
    print(manacher("abaaba"))                   # [0, 1, 0, 3, 0, 1, 6, 1, 0, 3, 0, 1, 0]
    print(longest_palindrome("forgeeksskeegfor"))   # geeksskeeg
    print(count_palindromes("aaa"), count_palindromes("abaaba"))   # 6 11
    q = PalindromeQuery("abaaba")
    print(q.is_palindrome(1, 4), q.is_palindrome(0, 3), q.is_palindrome(0, 2))   # True False True: baab, abaa, aba

06Practice

• LeetCode 5Longest Palindromic SubstringMedium
• LeetCode 647Palindromic Substrings (each centre contributes ⌈p / 2⌉)Medium
• LeetCode 132Palindrome Partitioning II (turn the DP's palindrome test into an O(1) query)Hard
• LeetCode 2472Maximum Number of Non-overlapping Palindrome SubstringsHard
• LeetCode 1960Maximum Product of the Length of Two Palindromic Substrings (Manacher plus prefix and suffix maxima)Hard
• LeetCode 3327Check if DFS Strings Are Palindromes (run Manacher over the tree's traversal order)Hard