Manacher longest palindromic substring: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Reuse mirrored palindrome radii inside the rightmost known palindrome, expanding only when necessary. Return the leftmost longest palindromic substring.

Insert zero separators between letter codes so odd and even palindromes share one representation. Within the rightmost palindrome, mirror a previously computed radius and expand only beyond what that mirror proves.

Open the 3D visualization

Manacher longest palindromic substring example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Manacher longest palindromic substring

Finding a longest palindromic substring in linear time, including long repetitive strings.

Choosing an alternative

Center expansion can require quadratic work; dynamic programming stores a quadratic palindrome table. Manacher stores one radius per transformed center.

Worked example: input and state changes

Example input

abacabadabacaba

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initial state.

    State at this checkpoint
    {
      "values": [
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": []
    }
  2. Step 20: Expand center 7 to radius 7.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        7,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [
        7
      ],
      "kind": "matrix",
      "columns": 12,
      "center": 3,
      "right": 6,
      "start": 0,
      "result": 3
    }
  3. Step 40: Expand center 15 to radius 6.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        7,
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        6,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [
        15
      ],
      "kind": "matrix",
      "columns": 12,
      "center": 7,
      "right": 14,
      "start": 0,
      "result": 7
    }
  4. Step 60: Finalize center 20; best substring starts at 0, length 15.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        7,
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        15,
        0,
        1,
        0,
        3,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [
        20
      ],
      "kind": "matrix",
      "columns": 12,
      "center": 15,
      "right": 30,
      "start": 0,
      "result": 15
    }
  5. Step 80: Longest palindrome: abacabadabacaba; start 0, length 15.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        7,
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        15,
        0,
        1,
        0,
        3,
        0,
        1,
        0,
        7,
        0,
        1,
        0,
        3,
        0,
        1,
        0
      ],
      "active": [],
      "kind": "matrix",
      "columns": 12,
      "center": 15,
      "right": 30,
      "start": 0,
      "result": 15,
      "substring": "abacabadabacaba"
    }

Expected final state

Longest palindrome: abacabadabacaba; start 0, length 15.

Complexity and input bounds

Family: Strings. Time complexity: O(n).

Implementation detail: The matrix displays transformed-center radii: even positions are separators and odd positions are letters. Downloads accept ASCII letter codes and return the maximum length, writing [start,length]. The empty download input returns [0,0]; the interactive view accepts 1..40 letters.

Space complexity: O(n) auxiliary space for transformed letters and radii; recorded animation snapshots use additional space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..40 ASCII letters, case sensitive.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A substring is contiguous; a subsequence is not. Mirror radii must be clipped at the known right boundary. This implementation is case sensitive and chooses the leftmost answer on ties.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// a contains n ASCII letter codes (65..90 or 97..122), 0..40 letters; case sensitive. Returns longest palindromic substring length and writes [leftmost_start,length] to output (capacity at least 2). Empty input returns 0 with [0,0]. Zero separators handle odd and even lengths uniformly. O(n) time and O(n) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, output) {
    let transformed = Array(256).fill(0); let radius = Array(256).fill(0); let m = 2 * n + 1; let center = 0; let right = 0; let start = 0; let length = 0; let mirror = 0; let candidate = 0;
    for (let i = 0; i < n; i++) { transformed[2 * i + 1] = a[i]; }
    for (let i = 0; i < m; i++) {
        if (i < right) { mirror = 2 * center - i; radius[i] = radius[mirror]; if (radius[i] > right - i) { radius[i] = right - i; } }
        while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < m && transformed[i - radius[i] - 1] == transformed[i + radius[i] + 1]) { radius[i]++; }
        if (i + radius[i] > right) { center = i; right = i + radius[i]; }
        candidate = (i - radius[i]) >> 1;
        if (radius[i] > length || (radius[i] == length && candidate < start)) { start = candidate; length = radius[i]; }
    }
    output[0] = start; output[1] = length;
    return length;
}

Source

Original linear-time palindrome research. The playground uses the standard mirrored-radius adaptation to longest palindromic substring, rather than reproducing the paper’s smallest-initial-palindrome interface.