Manacher's Algorithm — Radius Array in O(n)

The #-transform makes every palindrome odd. Watch the box [l, r], the mirror reuse p[i] = min(r−i, p[i']), and the expansion fill the radius array.

step 0

Transformed string t and radius array p[]

box [l, r] center i mirror i' expansion probe
Press Step to begin. We scan left to right computing p[i] = radius of the longest palindrome centered at i in t.
center i = — mirror i' = — box (c,l,r) = — p[i] = — longest = — count = 0

Original string s and current palindrome

The green span shows the current center's palindrome mapped back to s via start = (i − p[i]) / 2, length = p[i].

Algorithm (active line highlighted)


    

  


  
We compute the radius array of t in one linear pass. Inside the current box we copy from the mirror; otherwise we expand from scratch. The right edge r only moves forward, which is why the whole scan is O(n).


  

    Self-contained visualization. Real characters sit at odd indices of t; # separators sit at even indices.
    Radius p[i] in t equals the palindrome length in the original string; longest palindrome length = max p[i], and the count of all palindromic substrings = Σ ⌈p[i]/2⌉.
    See junior.md and professional.md for the mirror-initialization correctness and the O(n) proof.