Palindromes, Periodicity & Combinatorics on Words

Palindrome Baselines and Manacher Radii

A palindrome reads identically from left to right and right to left. Expanding independently around all centers takes $O(n^2)$ time, as does interval DP. Manacher's algorithm computes every maximal radius in $O(n)$ by maintaining the rightmost palindrome $[l,r]$ and reusing the radius at the mirrored center.

Let $d_{odd}[i]$ include the center of the longest odd palindrome at $i$, giving interval $[i-d_{odd}[i]+1,i+d_{odd}[i]-1]$. Let $d_{even}[i]$ be the radius centered between $i-1$ and $i$, giving $[i-d_{even}[i],i+d_{even}[i]-1]$. Inside $[l,r]$, the mirror radius is capped by the distance to $r$; comparisons are needed only beyond that guaranteed region.

def manacher_odd(text: str) -> list[int]:
    """Radius includes the center; palindrome length is 2*d[i]-1."""
    n = len(text)
    d = [0] * n
    left, right = 0, -1
    for i in range(n):
        radius = 1 if i > right else min(d[left + right - i], right - i + 1)
        while i - radius >= 0 and i + radius < n and text[i-radius] == text[i+radius]:
            radius += 1
        d[i] = radius
        if i + radius - 1 > right:
            left, right = i - radius + 1, i + radius - 1
    return d


def manacher_even(text: str) -> list[int]:
    """Center i lies between i-1 and i; palindrome length is 2*d[i]."""
    n = len(text)
    d = [0] * n
    left, right = 0, -1
    for i in range(n):
        radius = 0 if i > right else min(d[left + right - i + 1], right - i + 1)
        while i - radius - 1 >= 0 and i + radius < n and text[i-radius-1] == text[i+radius]:
            radius += 1
        d[i] = radius
        if i + radius - 1 > right:
            left, right = i - radius, i + radius - 1
    return d


def longest_palindrome(text: str) -> str:
    if not text:
        return ""
    best_start, best_length = 0, 1
    for center, radius in enumerate(manacher_odd(text)):
        length = 2 * radius - 1
        if length > best_length:
            best_start, best_length = center - radius + 1, length
    for center, radius in enumerate(manacher_even(text)):
        length = 2 * radius
        if length > best_length:
            best_start, best_length = center - radius, length
    return text[best_start:best_start + best_length]


if __name__ == "__main__":
    assert manacher_odd("abacaba") == [1, 2, 1, 4, 1, 2, 1]
    assert manacher_even("abba") == [0, 0, 2, 0]
    assert longest_palindrome("bananas") == "anana"
    for sample in ["", "a", "abba", "abacaba", "bananas", "aaaa"]:
        print(sample, manacher_odd(sample), manacher_even(sample), longest_palindrome(sample))

Palindromic Trees and Distinct Palindromes

An Eertree stores every distinct palindromic substring as one node. It starts with roots of lengths $-1$ and $0$. A transition labeled $c$ from palindrome $P$ leads to $cPc$, so appending one symbol creates at most one node and a length-$n$ string has at most $n$ distinct non-empty palindromes.

Maintain last, the longest palindromic suffix of the processed prefix. Follow suffix links until finding a suffix-palindrome extendable by the new symbol. Reuse its transition or create a node whose suffix link targets its longest proper palindromic suffix. Increment last on each append, then propagate counts from longer nodes to suffix-link parents to obtain total, overlapping occurrence counts.

flowchart TD
    NEG["Root: length -1"]
    ZERO["Root: length 0"]
    A["Palindrome a"]
    B["Palindrome b"]
    ABA["Palindrome aba"]
    BAB["Palindrome bab"]
    NEG -->|a| A
    NEG -->|b| B
    B -->|a| ABA
    A -->|b| BAB
    ZERO -. suffix .-> NEG
    A -. suffix .-> ZERO
    B -. suffix .-> ZERO
    ABA -. suffix .-> A
    BAB -. suffix .-> B

Borders, Periods, Covers, and the Fine-Wilf Theorem

A border is a proper prefix that is also a suffix. The prefix function exposes every border: start at $k=\pi[n-1]$ and repeatedly replace $k$ by $\pi[k-1]$. This is also the failure chain used by KMP.

An integer $p$ is a period when $S[i]=S[i-p]$ wherever both positions exist. A border of length $b$ induces period $n-b$, and period $p$ induces a border of length $n-p$. Thus $n-\pi[n-1]$ is the shortest-period candidate; the string is an exact power precisely when this value divides $n$. A cover is a substring whose overlapping occurrences cover every position, while a quasiperiodic string has a proper cover.

Runs and Tandem Repetitions

A repetition of period $p$ has exponent equal to its length divided by $p$. A square is $XX$, a cube is $XXX$, and a run is an interval of length at least $2p$ with shortest period $p$ that cannot be extended left or right while preserving that period.

One run may contain many square and cube occurrences. Nevertheless, a length-$n$ word has fewer than $n$ runs, enabling linear-size output and linear-time enumeration. Algorithms often combine longest-common-extension queries with Lyndon roots, canonical occurrences of primitive period words that anchor maximal repetitions.

Lyndon Factorization and Canonical Rotations

A Lyndon word is strictly smaller than each nontrivial rotation, equivalently smaller than every proper non-empty suffix. The Chen-Fox-Lyndon theorem uniquely factors every string into a non-increasing sequence of Lyndon words. Duval computes this factorization in $O(n)$ time and supports combinatorics-on-words and run algorithms.

A necklace is an equivalence class under rotation. Booth's algorithm finds a lexicographically minimum rotation in $O(n)$ by comparing candidate starts in $S+S$ and eliminating ranges after mismatches. Periodic inputs may have multiple equal minima, so an implementation should document its tie rule.