jsschools

Manacher's Algorithm

Finds the longest palindromic substring (and all palindrome radii) in linear O(n) time by exploiting palindrome symmetry to avoid redundant character comparisons.

Spec ↗

Syntax

manacher(s)

Parameters

NameTypeRequiredDescription
s string Yes The input string. The algorithm inserts separator characters internally to handle both odd- and even-length palindromes uniformly.

Returns

{ longest: string, start: number, length: number } — The longest palindromic substring with its starting index and length in the original string.

Examples

function manacher(s) {
  // Transform: 'abc' → '#a#b#c#'
  const t = '#' + s.split('').join('#') + '#';
  const n = t.length;
  const p = new Array(n).fill(0); // p[i] = palindrome radius at i in t
  let c = 0, r = 0; // center and right boundary of rightmost palindrome

  for (let i = 0; i < n; i++) {
    if (i < r) p[i] = Math.min(r - i, p[2 * c - i]);
    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] === t[i + p[i] + 1])
      p[i]++;
    if (i + p[i] > r) { c = i; r = i + p[i]; }
  }

  // Find max palindrome in original string
  let maxLen = 0, center = 0;
  for (let i = 0; i < n; i++) if (p[i] > maxLen) { maxLen = p[i]; center = i; }
  const start = (center - maxLen) / 2;
  return { longest: s.slice(start, start + maxLen), start, length: maxLen };
}

console.log(manacher('babad'));
console.log(manacher('cbbd'));
Output 
{ longest: 'bab', start: 0, length: 3 }
{ longest: 'bb', start: 1, length: 2 }

function manacher(s) {
  const t = '#' + s.split('').join('#') + '#';
  const n = t.length, p = new Array(n).fill(0);
  let c = 0, r = 0;
  for (let i = 0; i < n; i++) {
    if (i < r) p[i] = Math.min(r - i, p[2*c-i]);
    while (i-p[i]-1 >= 0 && i+p[i]+1 < n && t[i-p[i]-1] === t[i+p[i]+1]) p[i]++;
    if (i+p[i] > r) { c = i; r = i+p[i]; }
  }
  let mx = 0, ct = 0;
  p.forEach((v,i) => { if(v>mx){mx=v;ct=i;} });
  const st = (ct-mx)/2;
  return { longest: s.slice(st, st+mx), start: st, length: mx };
}

// Entire string is a palindrome
console.log(manacher('racecar'));
Output 
{ longest: 'racecar', start: 0, length: 7 }

Notes

| Case | Time | Space | |---------|------|-------| | Best | O(n) | O(n) | | Average | O(n) | O(n) | | Worst | O(n) | O(n) | The key insight is the **mirror property**: if i is within the right boundary r of the current rightmost palindrome centred at c, then p[i] can be initialised from its mirror p[2c - i] without rescanning. The transformed string (inserting '#' between every character) unifies odd and even palindromes, simplifying the implementation. Manacher's is optimal — any algorithm must read every character at least once. The p[] array encodes all palindromic substrings, not just the longest.

See also