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.
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.
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": [] }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 }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 }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 }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String
Glenn Manacher (1975). Original research paper.