Manacher and Eertree Compared

Two Different Palindrome Questions

Manacher’s algorithm and the Eertree summarize different aspects of palindromic structure. Manacher assigns a radius to every possible center, compactly representing every palindromic occurrence in a fixed string. An Eertree instead creates one node per distinct palindromic substring and maintains transitions and suffix links as characters arrive.

For a string $S$ of length $n$, let $d_1[i]$ be the number of odd palindromes centered at $i$. It represents lengths $1,3,\ldots,2d_1[i]-1$. Let $d_2[i]$ be the number of even palindromes centered between $i-1$ and $i$, representing lengths $2,4,\ldots,2d_2[i]$. These two arrays use $O(n)$ space even when $S$ contains $\Theta(n^2)$ palindromic occurrences.

An Eertree contains two roots: one of length $-1$, which simplifies boundary handling, and one of length $0$, which represents the empty palindrome. Every other node represents exactly one distinct non-empty palindrome. Since appending one character creates at most one new distinct palindrome, an Eertree for a length-$n$ string has at most $n+2$ nodes.

Manacher Revisited

Expanding independently from every center can repeat the same comparisons and take $O(n^2)$ time. Manacher avoids that repetition by maintaining the rightmost palindrome discovered so far as a half-open interval $[l,r)$. When a new center $i$ lies inside this interval, its mirror $j=l+r-i-1$ supplies an initial odd radius, capped by the distance to $r$. Only characters beyond the known boundary require new comparisons.

For even palindromes, the center is the gap before $i$. Its mirror index is $j=l+r-i+1$, but the same principle applies: reuse the portion certified by symmetry, expand beyond $r$, and replace the active interval only if the new palindrome reaches farther right.

Each successful expansion advances the right boundary, and reuse within the active interval performs no character comparisons. Because $r$ advances at most $n$ times in each pass, both radius arrays are computed in $O(n)$ time.

from typing import Sequence, TypeVar

T = TypeVar("T")


def manacher_odd(sequence: Sequence[T]) -> list[int]:
    """Return d1[i], where the longest odd palindrome has length 2*d1[i]-1."""
    n = len(sequence)
    radius = [0] * n
    left, right = 0, 0

    for center in range(n):
        if center < right:
            mirror = left + right - center - 1
            current = min(radius[mirror], right - center)
        else:
            current = 1

        while (
            center - current >= 0
            and center + current < n
            and sequence[center - current] == sequence[center + current]
        ):
            current += 1

        radius[center] = current
        if center + current > right:
            left = center - current + 1
            right = center + current

    return radius


def manacher_even(sequence: Sequence[T]) -> list[int]:
    """Return d2[i], where the longest even palindrome has length 2*d2[i]."""
    n = len(sequence)
    radius = [0] * n
    left, right = 0, 0

    for center in range(n):
        if center < right:
            mirror = left + right - center
            current = min(radius[mirror], right - center)
        else:
            current = 0

        while (
            center - current - 1 >= 0
            and center + current < n
            and sequence[center - current - 1] == sequence[center + current]
        ):
            current += 1

        radius[center] = current
        if center + current > right:
            left = center - current
            right = center + current

    return radius


def longest_palindrome(text: str) -> tuple[int, int, str]:
    """Return the start, exclusive end, and value of one longest palindrome."""
    if not text:
        return 0, 0, ""

    odd = manacher_odd(text)
    even = manacher_even(text)
    best_start, best_end = 0, 1

    for center, radius in enumerate(odd):
        start = center - radius + 1
        end = center + radius
        if end - start > best_end - best_start:
            best_start, best_end = start, end

    for center, radius in enumerate(even):
        start = center - radius
        end = center + radius
        if end - start > best_end - best_start:
            best_start, best_end = start, end

    return best_start, best_end, text[best_start:best_end]


def is_palindrome(left: int, right: int, odd: list[int], even: list[int]) -> bool:
    """Test the half-open substring [left, right) using precomputed radii."""
    if not (0 <= left <= right <= len(odd)):
        raise IndexError("substring is outside the sequence")
    length = right - left
    if length <= 1:
        return True
    if length % 2:
        center = (left + right - 1) // 2
        return odd[center] >= length // 2 + 1
    center = (left + right) // 2
    return even[center] >= length // 2


if __name__ == "__main__":
    text = "abacaba"
    odd = manacher_odd(text)
    even = manacher_even(text)

    assert odd == [1, 2, 1, 4, 1, 2, 1]
    assert even == [0, 0, 0, 0, 0, 0, 0]
    assert longest_palindrome(text) == (0, 7, "abacaba")
    assert is_palindrome(1, 6, odd, even)
    assert not is_palindrome(0, 6, odd, even)

    assert manacher_odd("abba") == [1, 1, 1, 1]
    assert manacher_even("abba") == [0, 0, 2, 0]
    assert longest_palindrome("abba") == (0, 4, "abba")
    assert manacher_odd("") == []
    assert manacher_even("") == []

Eertree Construction

An Eertree node stores a palindrome length, outgoing transitions, a suffix link, and usually an occurrence counter. A transition labeled $c$ from palindrome $P$ leads to $cPc$. The current last node represents the longest palindromic suffix of the processed prefix.

When appending $c=S[i]$, follow suffix links from last until reaching the longest suffix palindrome $P$ whose preceding symbol is also $c$. If its $c$-transition already exists, that target becomes the new last, and its occurrence counter increases. Otherwise, create the new palindrome $cPc$ of length $|P|+2$.

A new length-one palindrome links to the length-zero root. For a longer new palindrome, continue down suffix links from $P$ until another extendable suffix is found; the corresponding $c$-transition is the new node’s suffix link. Processing nodes later in decreasing length and adding each counter to its suffix-link parent converts suffix-ending counts into total occurrence counts.

flowchart TD
    A["Append character c at position i"] --> B{"Can current suffix P be extended by c?"}
    B -- "No" --> C["Follow suffix link of P"]
    C --> B
    B -- "Yes" --> D{"Does transition P --c--> Q exist?"}
    D -- "Yes" --> E["Set last = Q; increment Q count"]
    D -- "No" --> F["Create Q for cPc; set length = length(P) + 2"]
    F --> G{"Is length(Q) = 1?"}
    G -- "Yes" --> H["Link Q to the length-0 root"]
    G -- "No" --> I["Follow suffix links to the next c-extendable palindrome"]
    I --> J["Link Q to that node's c-transition"]
    H --> K["Set last = Q; increment Q count"]
    J --> K

Selection and Hybrid Uses

Choose Manacher when the complete text is available and the questions are center- or interval-oriented: find a longest palindromic substring, count all palindromic occurrences, test whether fixed substrings are palindromes, or provide $O(1)$ palindrome checks to a partitioning DP. Its flat arrays have small constants and predictable memory access.

Choose an Eertree when the text arrives incrementally or when distinct palindromes are first-class objects. Nodes can store first positions, occurrence counts, minimum partition values, or series-link metadata. This supports queries such as the number of distinct palindromes after every append, the longest palindromic suffix of each prefix, and online palindromic-factorization DP.

The structures can also cooperate. Manacher can provide fast interval-palindrome predicates for an offline algorithm, while an Eertree indexes distinct values and their suffix relationships. Neither automatically solves every reporting problem: the required output representation should determine which summary is appropriate.