Introduction

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(n2)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)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.

Try It

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">Type text below. Manacher's algorithm finds the <b>longest palindromic substring</b> in O(n) by reusing mirror symmetry.</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">current center</span>
  <span class="leg-item leg-boundary">boundary</span>
  <span class="leg-item leg-best">longest palindrome</span>
</div>
<div id="result" class="result"></div>
<div class="radius-label">Radius array <span class="radius-hint">(half-length of palindrome centered here)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Manacher's algorithm — O(n) longest palindromic substring.
// We use the standard trick of inserting '#' separators so both odd and even
// palindromes are handled uniformly in the transformed string T.
// e.g. "abacaba" -> "#a#b#a#c#a#b#a#"
//
// p[i] = radius of palindrome centered at T[i] (not counting center itself).
// Answer: find max p[i], map back to original string indices.

function manacher(s) {
  if (!s.length) return { p: [], bestStart: 0, bestLen: 0, T: '' };
  // Build transformed string
  const T = '#' + s.split('').join('#') + '#'; // length 2n+1
  const n = T.length;
  const p = new Array(n).fill(0);
  let c = 0, r = 0; // center and right boundary of rightmost palindrome
  let bestLen = 0, bestCenter = 0;

  for (let i = 0; i < n; i++) {
    const mirror = 2 * c - i;
    if (i < r) {
      p[i] = Math.min(r - i, p[mirror]);
    }
    // Attempt to expand around center i
    let a = i - (p[i] + 1);
    let b = i + (p[i] + 1);
    while (a >= 0 && b < n && T[a] === T[b]) {
      p[i]++;
      a--;
      b++;
    }
    // Update rightmost boundary
    if (i + p[i] > r) {
      c = i;
      r = i + p[i];
    }
    if (p[i] > bestLen) {
      bestLen = p[i];
      bestCenter = i;
    }
  }

  // Map back: center bestCenter in T, radius bestLen
  // In T, T[i] maps to original index (i-1)/2 (only for odd i = real chars).
  // The palindrome in T spans [bestCenter - bestLen, bestCenter + bestLen].
  // In original string: start = (bestCenter - bestLen) / 2, length = bestLen.
  const bestStart = (bestCenter - bestLen) / 2;
  return { p, bestStart, bestLen, T };
}

function render() {
  const raw = document.getElementById('txt').value;
  const s = raw.replace(/[^a-zA-Z0-9]/g, '').toLowerCase() || '';
  const { p, bestStart, bestLen, T } = manacher(s);

  // Find max radius index for highlight
  let maxR = 0, maxI = 0;
  for (let i = 0; i < p.length; i++) if (p[i] > maxR) { maxR = p[i]; maxI = i; }

  // Compute rightmost boundary in T-space at end of algorithm = center of max palindrome
  // (recompute for display: boundary after all iterations)
  let c = 0, r = 0;
  for (let i = 0; i < T.length; i++) {
    if (i + p[i] > r) { c = i; r = i + p[i]; }
  }
  const boundaryLeft = c - p[maxI]; // left edge of best palindrome in T
  const boundaryRight = c + p[maxI]; // right edge

  // Render character cells (T = transformed string)
  const vis = document.getElementById('vis');
  vis.innerHTML = '';
  const radiiEl = document.getElementById('radii');
  radiiEl.innerHTML = '';

  for (let i = 0; i < T.length; i++) {
    const isGap = (i % 2 === 0); // T[0], T[2], ... are '#'
    const inBest = (i >= maxI - maxR && i <= maxI + maxR);
    const isCenter = (i === maxI);
    const isBoundary = !isCenter && (i === maxI - maxR || i === maxI + maxR);

    const d = document.createElement('div');
    let cls = 'ch' + (isGap ? ' gap' : '');
    if (inBest && !isGap) cls += ' best';
    if (isBoundary) cls += ' boundary';
    if (isCenter) cls += ' center';
    d.className = cls;
    d.textContent = isGap ? '·' : T[i];
    vis.appendChild(d);

    const ri = document.createElement('div');
    ri.className = 'ri' + (isGap ? ' gap' : '') + (i === maxI ? ' best-r' : '');
    ri.textContent = isGap ? '' : p[i];
    radiiEl.appendChild(ri);
  }

  const res = document.getElementById('result');
  if (!s.length) {
    res.innerHTML = 'Type some text to begin.';
    return;
  }
  const palindrome = s.slice(bestStart, bestStart + bestLen);
  res.innerHTML = bestLen <= 1
    ? 'No repeated palindrome found (every single character is trivially one).'
    : fmt('Longest palindrome: <span>"%palindrome%"</span> (length %bestLen%, starting at index %bestStart%)', { palindrome: palindrome, bestLen: bestLen, bestStart: bestStart });
}

document.getElementById('txt').addEventListener('input', render);
render();
Result
Console

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)O(1), only boundary-pushers pay to expand.

The Real Complexity

How do we know Manacher runs in O(n)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)O(n) steps, giving O(n2)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)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)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)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.

Where It Matters

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)O(n) versus O(n2)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)O(n) work in one step.

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

Conclusion

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)O(1) mirror copies, and the total work collapses from O(n2)O(n^{2}) to O(n)O(n).

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

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/manacher/Content licensed under CC BY-NC 4.0.