Understanding Manacher's Algorithm for Longest Palindromic Substrings

A palindrome reads the same forwards and backwards. A longest palindromic substring is the longest contiguous block within a string that is palindromic; a palindromic subsequence may skip characters. Thus aba is a substring of abacaba, while a c a with spaces between its letters would be a subsequence. The answer may have odd length, such as racecar, or even length, such as abba.

Expanding around every possible centre gives an easy (O(n^2)) solution: check one character, then the pair around it, then the next pair. That work becomes wasteful on highly repetitive input such as aaaaaaaaaa, where each centre repeatedly confirms nearly the same span. The aim is to reuse a confirmed palindrome when the next centre lies inside it.

Manacher's Algorithm reaches (O(n)) time by assigning each position a radius and reflecting information from earlier centres. Its transformed representation lets the same machinery handle odd and even palindromes. This matters wherever string scanning occurs under real workloads: Australian transport apps handling Sydney's Opal cards, Melbourne's Myki cards and Brisbane's TransLink go card can validate identifiers, while search tools need to inspect user input quickly.

Why Longest Palindromic Substrings Matter

The output is one substring and its starting position, or a clear empty result for an empty string. A naïve solver compares characters outwards from all (2n-1) possible centres. Each comparison can succeed, so the runtime depends on both the number of centres and how far each expansion travels. That distinction between linear and quadratic work is central to choosing an algorithm.

Palindrome finding also differs from ordinary pattern search. A Boyer–Moore string matching tutorial explains how to locate a known pattern efficiently, while Manacher's method asks which symmetric span inside an unknown string is longest. Both exploit structure, but one compares a pattern against a text and the other compares characters around moving centres.

Australian market data provides practical examples: catalogues from Coles, Woolworths and smaller online retailers can contain product codes, promotional labels and customer-entered searches. Detecting a palindrome can expose duplicated fields or suspicious test values during data cleaning. It can also support instant feedback in search boxes, provided matching rules are explicit about case, spaces and punctuation.

The Core Idea Behind Manacher's Algorithm

The first transformation inserts a separator between every pair of characters and at both ends. abba becomes #a#b#b#a#, while aba becomes #a#b#a#. Every original palindrome now has one centre in the transformed sequence, whether its original length was odd or even.

For each transformed position, the radius records how many transformed positions can be included on either side of the centre. The palindrome runs from centre - radius to centre + radius. With this separator layout, the radius of the largest palindrome equals its length in the original string. A separate right boundary marks the furthest point reached by the palindrome currently centred at center.

When a new position sits inside that right boundary, its radius can begin as the radius of its mirrored position, limited by the distance to right. The algorithm then expands only as far as the copied information fails to predict a match. This mirror step prevents already-known matches from being checked again, which is the source of the linear running time.

Odd and Even Palindromes

An odd palindrome has a character at its centre: aba centres on b. An even palindrome has a gap at its centre: abba centres between the two b characters. Handling these separately is possible with an odd-radius array and an even-radius array, but it doubles some bookkeeping and makes the boundary cases harder to see.

The separator construction avoids that split. In #a#b#b#a#, the centre separator represents the gap in abba; in #a#b#a#, the centre b represents the character centre in aba. A single expansion can therefore cross a separator, stop at a mismatched character pair and cover both parity cases without special-case loops.

Language conventions matter as well: Australian English commonly uses optimisation and centre, so any case-folding or accent-normalisation policy must be deliberate. Characters must also remain ordinary data even when they resemble separators. A robust implementation should not assume that # is absent from the input, and it should define whether matching happens over Unicode code points or user-perceived characters. The word café, for example, may be stored as one precomposed character or as cafe followed by a combining accent.

Reusing Palindrome Information

Reuse begins with a reflection. If center is the active centre and i is the position being processed, its mirror is 2 * center - i. Inside the active palindrome, matching outer layers imply that the mirror position has a useful radius. The safe initial radius is the smaller of the mirrored radius and right - i.

Consider #a#b#a#c#a#b#a#. The large palindrome around the middle a establishes a wide right boundary. A later centre on the right reflects to an earlier centre with the same local shape, so the algorithm can copy that radius immediately. If expansion later crosses the old boundary, it compares additional character pairs one by one and then updates the active centre and boundary.

Each successful explicit comparison extends beyond the previously known right boundary, so there are only (O(n)) such comparisons in total. A counting sort guide demonstrates another linear-time algorithm, but its guarantee depends on a bounded range of keys; Manacher's method needs only equality comparisons. The reuse resembles KMP's treatment of a matched prefix, except the reusable structure here is symmetry around centres.

A Worked Example

For babad, first insert separators to obtain #b#a#b#a#d#. The a at original index one is a character centre. Its neighbours are both b, so its radius grows to three, corresponding to the original substring bab.

The other a also forms aba, producing another valid answer of length three. The d has no matching neighbouring character, so its radius remains small. The algorithm stores the first longest match unless it is explicitly configured to replace it when another equally long palindrome appears. Returning the earliest match is deterministic; returning the last requires changing the tie-breaking rule.

For abba, the transformed text is #a#b#b#a#. Expansion begins at the separator between the two b characters, reaches both a characters and identifies the full original word. For an empty input, the answer should be an empty substring with length zero; for a one-character input, the radius and returned length are both one.

Python Implementation and Complexity

The following Python implementation uses a list rather than a string for the transformed sequence, allowing None to represent separators safely. Any Python string is valid input, including one containing #. The function returns the earliest longest palindrome and its length.

def longest_palindromic_substring(text):
    if not text:
        return "", 0

    transformed = [None]
    for char in text:
        transformed.extend((char, None))

    radii = [0] * len(transformed)
    center = right = 0
    best_start = 0
    best_length = 0

    for i in range(len(transformed)):
        if i < right:
            mirror = 2 * center - i
            radii[i] = min(right - i, radii[mirror])

        while (
            i - radii[i] - 1 >= 0
            and i + radii[i] + 1 < len(transformed)
            and transformed[i - radii[i] - 1] == transformed[i + radii[i] + 1]
        ):
            radii[i] += 1

        if i + radii[i] > right:
            center = i
            right = i + radii[i]

        if radii[i] > best_length:
            best_length = radii[i]
            best_start = (i - radii[i]) // 2

    return text[best_start:best_start + best_length], best_length

Each radius starts from its mirrored value when possible, then expands with explicit bounds checks. The center and right pair describe the active palindrome, while best_start retains the earliest maximal answer. Python strings are immutable sequences, and the Python data model guide explains how built-in types cooperate through dunder methods and protocols, which is useful background when adapting the function to custom text objects.

The running time is (O(n)), and the transformed list and radius array use (O(n)) space. Empty and one-character inputs are handled without special expansion errors. The implementation also preserves case, punctuation and whitespace exactly, leaving those decisions to the caller.

Practical Use and Validation

Practical deployment begins with rules. Australian phone numbers commonly use 04 plus eight digits for mobiles and +61 for international form, while postcodes contain four digits. If a service checks malformed customer data, a palindrome rule should be a narrow validation signal rather than an automatic rejection rule, since valid identifiers can accidentally be symmetric.

Case folding can change results: NOON and noon match either way, but mixed punctuation and spaces need a normalisation policy. Australian English spellings such as optimisation and centre should remain unchanged unless the application explicitly canonicalises language. Unicode normalisation matters for names and labels containing accented characters, including many used across Australian communities.

At scale, the linear scan suits autocomplete, duplicate detection, formatting checks and educational tools. Testing should include empty strings, repeated characters, alternating characters, odd and even palindromes, punctuation and non-ASCII text. With those cases covered, Manacher's Algorithm turns a seemingly quadratic search into a predictable linear procedure built from a small, reusable symmetry invariant.