Every other Exact Match entry on this site answers the same
question: given a pattern, where does it occur in a text? Manacher's algorithm
answers a different one entirely — given one string, what is its longest palindromic
substring, with no separate pattern at all? Checking every substring naively (there are
O(n²) of them, each an O(n) palindrome check) costs
O(n³). Expanding outward from every possible center — a real character or the
gap between two characters, 2n−1 centers in all — cuts that to
O(n²), since each expansion is at worst O(n) but most centers stop
almost immediately. Manacher's algorithm gets to O(n) by noticing that a palindrome
already found has an exploitable symmetry: everything already confirmed on one side of its center
has a mirror-image twin already confirmed on the other side, so large stretches of new centers can
reuse an old answer instead of re-expanding from scratch.
The trade going in: this page finds a longest palindromic substring (ties are real — several different substrings can share the maximum length, and the reference implementation below simply keeps the first one it finds) in guaranteed linear time, with no dependency on the alphabet size. It answers a structurally different question from string matching, so it isn't compared against the other eleven exact-match entries in Choosing an Exact-Match String Matcher — see that guide for why, the same way it already sets Mo's Algorithm and three others aside from its own six-way range-query comparison.
Enter a text (lowercase letters only, up to 16 characters) and press
Build. The algorithm first transforms the text by inserting a #
between every character and adding ^/$ sentinels at both ends — this
turns every palindrome, odd or even length, into an odd-length palindrome in the transformed
string, so one piece of code handles both cases. It then fills a radius array P
left to right: P[i] is how far the palindrome centered at transformed-position
i extends on each side. Step through the build to watch each position either
copy a free starting estimate from its mirror across the current center, or
start fresh from zero, before expanding as far as it verifiably can. The
skip the mirror cap (bug) checkbox reproduces a real, checked bug — see
Pitfalls.
The transform matters because it unifies odd- and even-length palindromes into one shape. In
the original string, a palindrome is centered either on a character (odd length) or on the gap
between two characters (even length) — two different cases a naive implementation has to handle
separately. After inserting # everywhere, every one of those centers becomes a real
position in the transformed string, and every palindrome in the transformed string has odd length
by construction: expanding outward from any center, the characters and separators alternate in
mirror image regardless of whether the original palindrome was odd or even. The
^/$ sentinels exist purely so the expansion never has to check "did I run
off the end of the array" as a separate condition — see Pitfalls for exactly what goes wrong
without them.
The linear-time trick keeps a running center C and the rightmost boundary
R = C + P[C] that any palindrome found so far has reached. For a new position
i inside that boundary (i < R), its mirror across C is
2C − i — and because the whole span [C−P[C], C+P[C]] is
already known to be a palindrome, whatever radius was found at the mirror position is guaranteed
to also hold at i, up to the edge of that known span. Past that edge, nothing
has actually been compared yet for this alignment, so the initial estimate must be capped at
R − i — copying more than that would claim knowledge about text the algorithm
has never looked at. After that free (possibly zero) starting estimate, the algorithm always tries
to expand further with real character comparisons, exactly the same expand-around-center step a
naive approach would run — the difference is only ever in how big a head start each center gets
before that expansion begins. Every comparison either extends the boundary R past
where it has ever been before (bounded by n total extensions across the whole run) or
fails once and stops (bounded by n, one failure per position) — the same amortized
accounting this site's Z-Algorithm page uses for its own
window, applied here to palindromic symmetry instead of a repeated prefix.
This is the exact algorithm the demo above steps through:
function transform(s) {
const t = ['^', '#'];
for (const c of s) { t.push(c); t.push('#'); }
t.push('$');
return t;
}
function longestPalindrome(s) {
const t = transform(s);
const n = t.length;
const P = new Array(n).fill(0);
let C = 0, R = 0;
let bestLen = 0, bestStart = 0;
for (let i = 1; i < n - 1; i++) {
const mirror = 2 * C - i;
if (i < R) P[i] = Math.min(R - i, P[mirror]); // capped copy -- see Pitfalls
while (t[i + P[i] + 1] === t[i - P[i] - 1]) P[i]++;
if (P[i] > bestLen) { bestLen = P[i]; bestStart = Math.floor((i - P[i]) / 2); }
if (i + P[i] > R) { C = i; R = i + P[i]; }
}
return s.substr(bestStart, bestLen);
}Verified against brute-force enumeration of every substring across 269,813 strings tested exhaustively (2- and 3-letter alphabets, lengths 1 through 11) before this went on the page: zero mismatches on result length, zero results that weren't actually palindromes, and zero results not actually found at the reported position in the source string.
Skipping the cap on a mirrored copy produces a result that isn't even a
palindrome — a checked bug, not a hypothetical one. The skip the mirror cap
checkbox above removes exactly the Math.min(R - i, ...) from the line marked in the
reference implementation, copying P[mirror] directly instead. On this page's own
default text, "babaaa", the correct algorithm reports "bab" (length
3); with the cap removed, it reports "abaaa" (length 5) — which is not a
palindrome at all (reversed, it reads "aaaba"). The mechanism: at transformed position
i=6, mirroring across center C=4 gives mirror position 4
with P[4]=3, but the boundary is only confirmed out to R=7, two short of
what a full, uncapped copy would claim. The correct algorithm caps the estimate at
R−i=1 and then re-verifies by comparing real characters past that point, which
immediately fails; skipping the cap accepts the mirror's full radius as already proven and
expansion continues from a starting point that was never actually checked against the live text.
Across all 805,350 binary- and ternary-alphabet strings up to length 12 tested, the two versions
disagreed on 133,750 of them (16.6%) — not a rare edge case.
The ^/$ sentinels aren't cosmetic — removing them causes an
infinite loop, not a wrong answer, in this reference implementation's own language.
Without a distinct sentinel at each end, the expansion condition t[i + P[i] + 1] === t[i -
P[i] - 1] can walk both index arguments past the ends of the array at the same step.
JavaScript's array indexing doesn't throw on an out-of-range index — it returns
undefined — and undefined === undefined is true, so the loop
reads that as a match and keeps expanding forever. Tested directly against a version of this exact
function with the sentinels removed (leaving only # separators): "aba",
"a", "aa", and "racecar" all hang immediately once expansion
reaches the string's true boundary; only inputs where no palindrome ever reaches an edge happen to
terminate anyway. A language with bounds-checked array access would turn this into a crash instead
of a hang — either way, the fix is the same: give both ends of the array a character value that
never legitimately appears anywhere else in it.
Time: O(n), by the same amortized argument any Z-algorithm-style
window gets — each of the n transformed positions contributes at most one failed
comparison, and every successful comparison extends R past a point it has never
reached before, so the total comparison count across the whole run is bounded by 2n
regardless of the input. Measured directly, not just asserted: on twenty copies of the same
character (the case where every naive approach does the most redundant work), the algorithm above
needs exactly 39 character comparisons; an expand-around-every-center approach
that never reuses a mirrored result needs 400 for the identical input — a gap that
only widens as the input grows, since the naive approach stays O(n²) while this
one stays linear. Space: O(n) for the transformed string and the
radius array, both roughly twice the length of the original text.
This is the same "reuse a proven result instead of recomputing it" idea behind this site's Z-Algorithm and KMP pages, landing on a different kind of symmetry: those two reuse a repeated prefix found earlier in a scan; this one reuses a mirror image around a palindrome's own center. See Choosing an Exact-Match String Matcher for why this page sits outside that guide's nine-way comparison rather than joining it.