Manacher's Algorithm

A palindrome is a string that reads the same forwards and backwards: racecar, level, abacaba. Finding whether one hides inside a longer string sounds like a simple scan — until you realise you might have to check every possible center and expand in both directions, costing $O(n^{2})$ time on an n-character string.

In 1975, Glenn Manacher published a one-page algorithm that solved the problem in $O(n)$ — strictly linear, no matter the input. The idea is almost embarrassingly elegant: if you already know a palindrome spans positions l to r, then any character inside it has a mirror on the other side. You already know how far the mirror's palindrome reaches. Why expand from scratch?

Manacher's algorithm keeps a running rightmost palindrome boundary and reuses every previously computed radius. Each character is visited at most twice — once when the boundary moves right, once when it is mirrored — so the total work stays linear. It is a case study in how a single structural insight collapses an apparently quadratic problem to linear.

Type any text below. The demo runs Manacher's algorithm and highlights the longest palindromic substring in real time, showing the radius array and the current rightmost boundary.

<div class="hint">{{hint}}</div>
<div class="input-row">
  <input id="txt" type="text" value="abacaba" maxlength="40" spellcheck="false" autocomplete="off" />
</div>
<div id="vis" class="vis"></div>
<div class="legend-row">
  <span class="leg-item leg-center">{{leg_center}}</span>
  <span class="leg-item leg-boundary">{{leg_boundary}}</span>
  <span class="leg-item leg-best">{{leg_best}}</span>
</div>
<div id="result" class="result"></div>
<div class="radius-label">{{radius_label}} <span class="radius-hint">{{radius_hint}}</span></div>
<div id="radii" class="radii"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin-bottom: .6rem; line-height: 1.45; }
.input-row { margin-bottom: .7rem; }
#txt { font: 700 18px ui-monospace, monospace; padding: .4rem .7rem; border: 1.5px solid #c0c8d4;
       border-radius: 8px; width: 100%; max-width: 420px; color: #1d3557; background: #f5f8fb; }
.vis { display: flex; flex-wrap: nowrap; gap: 3px; margin-bottom: .3rem; overflow-x: auto; padding-bottom: 2px; }
.ch { min-width: 30px; height: 36px; display: flex; align-items: center; justify-content: center;
      font: 700 16px ui-monospace, monospace; border-radius: 6px; background: #e8eef3;
      border: 1.5px solid #c9d4de; color: #1d3557; transition: background .15s; }
.ch.best { background: #d0f0e0; border-color: #5cb87e; color: #0a5e30; }
.ch.boundary { background: #fff3cd; border-color: #e8b628; color: #7a5a00; }
.ch.center { background: #dde8ff; border-color: #5d7de8; color: #1a2f8a; }
.ch.gap { color: #aaa; font-size: 11px; background: #f0f2f5; border-color: #dde0e5; min-width: 22px; }
.legend-row { display: flex; gap: .8rem; flex-wrap: wrap; margin: .4rem 0 .6rem; }
.leg-item { font-size: .78rem; padding: 2px 8px; border-radius: 4px; font-weight: 600; }
.leg-center { background: #dde8ff; color: #1a2f8a; border: 1px solid #5d7de8; }
.leg-boundary { background: #fff3cd; color: #7a5a00; border: 1px solid #e8b628; }
.leg-best { background: #d0f0e0; color: #0a5e30; border: 1px solid #5cb87e; }
.result { font-weight: 700; font-size: 1rem; color: #1d3557; min-height: 1.4em; margin-bottom: .5rem; }
.result span { color: #0a7d33; }
.radius-label { font-size: .82rem; font-weight: 600; color: #555; }
.radius-hint { font-weight: 400; color: #888; }
.radii { display: flex; flex-wrap: nowrap; gap: 3px; margin-top: .3rem; overflow-x: auto; }
.ri { min-width: 30px; height: 26px; display: flex; align-items: center; justify-content: center;
      font: 600 13px ui-monospace, monospace; border-radius: 5px; background: #f0f2f5;
      border: 1px solid #dde0e5; color: #555; }
.ri.gap { min-width: 22px; color: #ccc; background: #fafafa; border-color: #eee; }
.ri.best-r { background: #d0f0e0; border-color: #5cb87e; color: #0a5e30; font-weight: 700; }

// Code not found

Watch how the boundary (the right edge of the farthest-reaching palindrome found so far) advances. Each time a new center extends past it, the boundary jumps; all centers inside it can copy their mirror's radius directly — no expansion needed. That is the saving: most characters pay $O(1)$, only boundary-pushers pay to expand.

How do we know Manacher runs in $O(n)$?

• Naive approach: for each of n centers (and n−1 between-character gaps), expand left and right until the palindrome breaks. Worst case — the string "aaa…a" — every expansion takes $O(n)$ steps, giving $O(n^{2})$ total.
• Manacher's key invariant: maintain the center c and right boundary r of the rightmost palindrome seen so far. For a new center i < r, the mirror position i' = 2c − i already has a known radius p[i']. If the mirror's palindrome fits entirely inside [l, r], then p[i] = p[i'] with no expansion. Only when the palindrome might extend past r do we expand — and each such expansion moves r strictly right.
• Amortized $O(n)$: r starts at 0 and ends at most n. Every unit of expansion moves r one step right, so expansions total at most n. Combined with the $O(1)$ mirror copies, the full algorithm is Θ(n).
• Status: Manacher's algorithm is a proven optimal solution to the longest palindromic substring problem. The problem has an Ω(n) lower bound (you must read every character), so $O(n)$ is tight. No asymptotically faster algorithm exists.

The algorithm is also a natural companion to pattern matching: both exploit the structure of previously computed information to avoid redundant work, in the same spirit as the KMP failure function.

Palindromic structure turns up in more places than party tricks:

• Bioinformatics: palindromic sequences in DNA (where a strand's complement reads the same in the opposite direction) are recognition sites for restriction enzymes. Finding all palindromic substrings quickly is a real biological task.
• Text compression: many compression algorithms exploit repeated and symmetric substrings; the radius array from Manacher is a compact summary of all palindromic structure in a string.
• String libraries: production string-processing libraries (in competitive programming judges, search engines, and text editors) use Manacher or its conceptual descendant, Eertree (palindromic tree), to answer palindrome queries in batch.
• Competitive programming: Manacher's algorithm is a standard tool in algorithmic contests — dozens of problems reduce to "find a palindromic substring with some property," and $O(n)$ versus $O(n^{2})$ is the difference between passing and timing out.
• Teaching amortized analysis: the algorithm is a textbook example of how a potential-function argument (tracking the rightmost boundary as a "credit") proves a non-obvious linear bound on a loop that sometimes does $O(n)$ work in one step.

Understanding Manacher means understanding amortized analysis — the same technique that shows why dynamic arrays double in $O(1)$ amortized time and why union-find runs near-linearly.

Manacher's algorithm is a lesson in what invariants can do. The naive palindrome search wastes work because it forgets: every expansion throws away information the next center could have used for free. By tracking the rightmost boundary, Manacher turns that forgotten knowledge into $O(1)$ mirror copies, and the total work collapses from $O(n^{2})$ to $O(n)$.

The result has been known since 1975 and is now optimal — you cannot find the longest palindromic substring faster than $O(n)$ without reading fewer characters. What looks like a string puzzle turns out to have a perfect solution hiding in its own symmetry.