Manacher: Let the Mirror Answer, and Palindromes Take One Pass

Finding palindromes looks simple at first. Choose a centre, expand equally to the left and right, and stop when the characters no longer match. Repeat that process for every possible centre.

The difficulty is that neighbouring centres often inspect the same characters again. If a long palindrome has already been discovered, expanding another centre inside it may retrace work that the first expansion has already established.

Manacher’s algorithm avoids most of that repetition. It remembers one palindrome that reaches furthest to the right, uses symmetry to answer new centres from their mirrored positions, and performs fresh comparisons only when the remembered information is not enough. The result is a single pass in total, with running time $O(n)$ for an input of length $n$.

This article develops the idea with a seven-character example. The main themes are:

• making odd- and even-length palindromes look like one problem;
• locating the mirror of a centre inside a known palindrome;
• copying a radius when symmetry makes that safe;
• clamping the copied radius at the known palindrome’s right edge;
• understanding why the apparently nested expansion loop still costs only $O(n)$ overall.

1. The repeated-work problem​

A palindrome reads the same from left to right and right to left. For example, abacaba is a palindrome because the outside characters match, the next pair matches, and so on:

abacaba
^^^^^^^

The centre is the character c. Moving one position outward gives a on both sides, then b, then a.

A direct method can inspect every possible centre. For each centre, it compares characters at equal distances from that centre. If the input has length $n$, there are roughly $n$ character centres, plus roughly $n$ gaps between characters. A long expansion around many of those centres can cause the same text positions to be examined repeatedly.

Imagine a text containing a long palindrome. A straightforward centre-expansion method may rediscover the same matching pairs for many nearby centres. The work is not wrong, but it ignores a useful fact: once a region has been verified as a palindrome, its internal positions are related by reflection.

For example, suppose a known palindrome is centred at C. A position just to the right of C has a corresponding position the same distance to the left. The text around those two positions is reflected. If the radius around one position has already been computed, some of that radius can be reused around the other position.

Manacher’s algorithm stores that information in a compact form. At any point, it maintains a palindrome with the rightmost known boundary. Call its left boundary $L$, its right boundary $R$, and its centre $C$. The interval from $L$ through $R$ is the current furthest-reaching window.

The important property is not merely that this palindrome is long. It is that its right edge is as far right as any palindrome discovered so far. This right edge gives the algorithm a boundary for deciding how much of a new centre can be answered by symmetry.

2. One representation for odd and even palindromes​

Palindromes come in two shapes.

An odd-length palindrome has a character at its centre. In aba, the centre is b.

An even-length palindrome has a gap at its centre. In abba, the centre lies between the two b characters.

If an algorithm handles these as two separate cases, its central logic becomes more complicated. Manacher’s method makes them one problem by inserting separators between characters and at the ends.

Take the seven-character string:

abacaba

Insert a separator, represented here by #, between every pair of characters and also at both ends:

#a#b#a#c#a#b#a#

The transformed string has one position for every original character and one separator position around it. For an original input of length $n$, this representation has $2n+1$ positions when only separators are used. The exact boundary markers used by an implementation may vary, but the central idea is the same: every possible palindrome centre becomes a position in the transformed string.

The original odd-length palindrome aba becomes:

#a#b#a#

Its centre is the original character b, which is also a position in the transformed string.

The original even-length palindrome abba becomes:

#a#b#b#a#

Its centre is the separator between the two b characters. The separator is now an ordinary centre position, so the expansion rule is identical for both cases: compare the position one step to the left with the position one step to the right, then continue outward while they match.

This transformation does not make the palindrome itself longer in a meaningful sense. It changes the coordinate system so that an odd centre and an even centre can be processed uniformly. The algorithm can therefore maintain one radius value for every transformed position.

The separator is a modelling device, not a new character that should appear in the answer. Once the radius array has been computed, an implementation can map transformed intervals back to ranges in the original string. That conversion depends on the precise radius convention, but the symmetry calculation is the same for both centre types.

3. What a radius means​

Let the transformed string be $T$. For a centre $i$, define its radius $P[i]$ as the number of matching expansion steps around $i$.

The first comparison checks:

If they match, the radius becomes at least $1$. The next comparison checks positions $i-2$ and $i+2$, and so forth. In general, an expansion of radius $k$ means that the positions at distances $1$ through $k$ on both sides match.

For the transformed string of abacaba:

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
value:  # a # b # a # c # a  #  b  #  a  #

The centre of the whole transformed palindrome is index $7$, the position containing c. It can expand seven positions in both directions, reaching index $0$ on the left and index $14$ on the right. Thus its radius is $7$ under this definition.

The corresponding palindrome interval is:

For this centre:

The radius array is useful because it records the answer for every transformed centre. A radius at a character centre describes an odd-length palindrome in the original text. A radius at a separator centre describes an even-length palindrome.

The transformation therefore removes a source of repeated case handling. The algorithm still has to process all transformed positions, but the transformed length is linear in the original length, so a linear pass over it remains $O(n)$.

A consistent radius definition matters. Some implementations store the number of successful comparisons, as in this article. Others use a closely related length or half-length convention. The mirror formula and boundary calculations are correct only when they match the selected definition.

4. The furthest-reaching window​

The central optimization is a maintained window $[L,R]$.

At a given stage, $[L,R]$ is the palindrome known so far whose right endpoint $R$ is furthest to the right. Its centre is $C$. Because the interval is a palindrome, positions inside it have reflected positions across $C$.

For a new centre $i$ inside the window, its mirror is:

The same relationship can be written using the boundaries:

These expressions are equal because $C$ is the midpoint of $L$ and $R$:

The mirror is not a separate approximation. It is the exact position obtained by reflecting $i$ across the centre of the known palindrome.

Suppose the known interval is symmetric and the radius at the mirror position is already $P[mirror]$. The text around $i$ reflects the text around mirror for as long as both positions remain inside the known interval. Therefore, some or all of the mirror’s radius can be copied to $i$ without performing fresh character comparisons.

This is the moment when the mirror answers the new centre.

The window is valuable because it provides both symmetry and a proof boundary. Symmetry explains why information from the mirror is relevant. The right edge explains where that information stops being guaranteed. Manacher’s algorithm needs both ideas; copying a radius without tracking the edge would be unsafe.

5. A small mirror example​

Use the transformed form of abacaba again:

#a#b#a#c#a#b#a#

The full palindrome has centre $C=7$, boundaries $L=0$ and $R=14$. Consider centre $i=9$, which lies inside the window.

Its mirror is:

Centre $5$ is the reflected position of centre $9$. The substring around centre $5$ is reflected around centre $7$ to produce the substring around centre $9$. If centre $5$ has a known radius that stays within the boundaries $L=0$ and $R=14$, centre $9$ can inherit that information.

Without the mirror rule, the algorithm might compare positions around centre $9$ from the beginning. With the rule, it starts with a radius already known to be valid.

This copied radius is not a guess based on the original characters alone. It is justified by the symmetry of the already verified palindrome. The work has effectively been transferred from the earlier centre to the new centre.

The same calculation works for a separator centre. For instance, if a separator lies to the right of the main centre, its mirror is a separator at the corresponding distance to the left. Thus the algorithm does not need one mirror formula for odd palindromes and another for even palindromes.

6. Why the copied radius must be clamped​

The mirror does not always provide the complete answer. This is the most important boundary detail in Manacher’s algorithm.

Suppose a new centre $i$ is inside the current window $[L,R]$. The mirror radius $P[mirror]$ may extend beyond the right boundary when reflected onto $i$. The known palindrome only proves matching text inside its own interval. It says nothing about positions beyond $R$.

Therefore, the safe initial radius is:

The term $R-i$ is the distance from the new centre to the known right edge. If the mirror radius is smaller, the entire mirror result fits inside the known window. If the mirror radius is larger, the copy must stop at the edge.

Case one: the mirror fits​

If:

then the mirror’s known palindrome lies completely inside the current window when reflected. The radius can be copied directly:

No expansion beyond that radius is required by the window information. The symmetry has answered the centre.

Case two: the mirror reaches the edge​

If:

then copying the entire mirror radius would claim matching characters beyond $R$. Those characters have not been established by the current window. The safe value is only:

The algorithm may then attempt fresh expansion beyond $R$. This is where new information can be discovered.

Case three: the mirror ends exactly at the edge​

If:

the mirrored palindrome reaches exactly to the boundary. The initial radius is valid, but the algorithm may still compare the next pair outside the window. A successful comparison extends the known window; a mismatch leaves the radius as it is.

The clamp is essential because symmetry is bounded by the region already known to be a palindrome. The mirror can answer for free only inside that region. At the edge, the algorithm must verify anything farther out.

A useful mental model is to regard the copied radius as a guaranteed lower bound, not always as the final answer. If it stops strictly before the right edge, it may already be complete because the corresponding mirrored structure also stops inside the known window. If it reaches the edge, the algorithm must test what lies beyond the frontier.

7. The two phases at each centre​

For every transformed position $i$, Manacher’s logic can be understood as two phases.

Phase one: obtain a safe initial radius​

If $i$ lies to the right of the current boundary, there is no known window covering it. Start with radius $0$ and expand normally.

If $i$ lies inside the current window, calculate its mirror:

Then initialize:

This may already be the final answer for $i$, or it may be only a lower bound that needs verification beyond $R$.

Phase two: expand beyond the safe radius​

After initialization, compare the next characters outside the currently known radius. In symbolic form, the next comparison is between:

and

If they match, increase $P[i]$ by $1$ and try again. If they differ, stop expansion for this centre. Boundary checks are also required so the algorithm does not read beyond the transformed string.

If the new palindrome around $i$ extends farther right than $R$, update the window:

The window is updated only when a centre establishes a farther right endpoint. A palindrome that ends before the current $R$ cannot improve the information used by later centres.

This separation between initialization and expansion makes the algorithm easier to reason about. Initialization reuses proven information. Expansion is reserved for checking characters that the current window has not already covered.

8. Walking through a seven-character string​

Let the original input be:

abacaba

The transformed text is:

#a#b#a#c#a#b#a#

The centre at the c position discovers a very large palindrome. Its boundaries become the beginning and end of the transformed string:

Now consider later centres, such as the a after c or the separator between that a and b. These centres lie inside the known window. Their mirrors lie on the other side of c.

For each one, the algorithm does not immediately start comparing from radius $0$. It looks at the mirror’s stored radius and clamps it using the distance to $R$. Much of the local structure is therefore inherited.

For example, at centre $i=9$, the mirror is $5$:

At centre $i=11$, the mirror is $3$:

The original text is symmetric around the central c, so the patterns around these pairs of centres correspond. The radius array records the result once it has been established, and later centres can use those values through their own mirrors.

The example is deliberately a complete seven-character palindrome because it makes the reflection visible. The same process applies when the current window is only a smaller palindrome inside a larger, non-palindromic string. In that situation, the right edge becomes even more important: it marks exactly how far the current symmetry has been verified.

Consider a centre just inside such a smaller window. Its mirror may have a large radius, but the reflected copy could run into text beyond the known right edge. The algorithm copies only up to the edge and then checks the actual text. If the text continues the palindrome, the window expands. If not, the centre keeps the safe radius it already inherited.

9. Why the expansion loop is not quadratic​

The code structure can look suspicious. There is a loop over every centre, and inside it there is another loop that expands while characters match. A first impression might be $O(n^2)$.

The key is that the inner loop does not repeatedly charge every successful comparison to the centre where it occurred. Successful expansions move the global right boundary $R$ to the right. Since $R$ can move from the beginning of the transformed string to its end only once, the total number of successful expansions across the whole algorithm is linear.

There can also be failed comparisons. A centre may use a copied radius and then make one comparison that fails immediately. Across the linear number of centres, these stopping comparisons contribute only a linear amount as well.

The amortized accounting is therefore:

The transformed string has linear size relative to the original seven-character-style representation. Consequently, the total running time remains:

The nested appearance is not the same as nested repeated work. The mirror initialization prevents expansions from restarting unnecessarily, while the furthest-reaching boundary ensures that new successful comparisons advance a global frontier rather than repeatedly exploring already covered text.

This is an amortized argument. It does not claim that every individual centre takes constant time. One centre may perform many comparisons. The claim is that the expensive comparisons make global progress, so the sum of their costs over the complete scan is linear.

10. A useful potential-function view​

Another way to understand the same argument is to track the right boundary as a potential.

Every time a fresh comparison succeeds beyond the current radius, the known palindrome reaches farther right. Thus $R$ increases. The transformed string has only a linear number of positions, so $R$ can increase only linearly many times.

When a comparison fails, the current centre’s expansion stops. There is no long sequence of successful expansions to charge to that failed comparison. Since the algorithm processes each centre once, the number of such failures is also linear.

This separates two kinds of work:

1. Inherited work, represented by the mirror radius. This work was already established elsewhere and is reused.
2. New work, represented by comparisons beyond the current window. Successful new work advances $R$; unsuccessful new work ends a centre’s expansion.

The algorithm’s efficiency comes from ensuring that inherited work is not repeated and that new work has a limited global budget.

The potential-function view is particularly useful when explaining why visual nesting in code can be misleading. A local loop may run many times, but each successful iteration increases a quantity that cannot increase indefinitely. The total is bounded by the size of the transformed string.

11. Why the rightmost window matters more than any window​

Manacher’s method could remember many palindromes, but the rightmost one is the most useful for scanning from left to right. A centre that lies before $R$ can potentially use the current window’s symmetry. A centre beyond $R$ cannot, because no known palindrome reaches it yet.

If a newly discovered palindrome ends at position $R'$, there are two possibilities:

• If $R'\leq R$, the current window remains the best right-reaching window.
• If $R'>R$, replace the current window with the new one.

The left edge $L$ is needed to identify the reflected structure, but the right edge $R$ determines whether new work is required. This explains why clamping uses $R-i$ rather than simply copying the mirror radius.

A mirror radius may describe a palindrome that is valid in its own location but whose reflected copy would run past the boundary of the current rightmost window. Beyond that boundary, the algorithm must inspect the actual transformed text.

The choice of a rightmost window also matches the direction of the scan. Centres are processed from left to right, so information that reaches farther right can help more future centres. A palindrome ending earlier may still be useful as a stored radius, but it cannot provide a better frontier for upcoming positions.

12. Recovering odd and even palindromes​

The transformed radius array stores information in a single coordinate system. To interpret it in the original string, distinguish the kind of transformed position.

If a centre corresponds to an original character, its palindrome has odd length in the original text. If a centre corresponds to a separator, its palindrome has even length.

For example, in:

#a#b#c#

The centre at b represents the odd palindrome b, and a centre at a separator represents a possible even palindrome whose two sides begin across that separator.

The exact conversion from a transformed radius to an original substring depends on the radius convention and the chosen separator representation. The important algorithmic fact is independent of that conversion: both types of centre receive a radius through the same mirror-and-expand procedure.

This uniform representation is especially helpful when the goal is not merely to test one fixed substring, but to record palindrome information around every possible centre. A caller can then interpret the radius array according to whether it needs odd palindromes, even palindromes, longest palindromes, or all centre-based palindrome extents.

For a longest-palindrome task, one can track the transformed centre with the largest radius or the widest transformed interval. For a centre-based query, the radius array provides the local extent directly. The algorithm’s core scan does not change; only the way its results are consumed changes.

13. Practical implementation decisions​

Although the core idea is mathematical, several implementation choices follow directly from it.

Choose a separator that cannot be confused with input characters​

The inserted separator should not accidentally behave like an ordinary input character. The purpose of the separator is to mark the gaps and make the transformed positions unambiguous. An implementation may also add boundary sentinels to simplify comparisons, but the supplied algorithmic idea does not depend on one particular sentinel spelling.

If the input alphabet can contain every ordinary character, the separator must be selected or represented so that it cannot be mistaken for real input. Otherwise, comparisons around a separator could accidentally treat a genuine input character as a structural marker.

Keep the radius convention consistent​

Some descriptions define the radius as the number of successful outward matches. Others use a related length convention. Either can work, but the formulas for the window boundaries and the expansion positions must agree with the chosen definition.

For the convention used here:

and the next comparison is made at distance $P[i]+1$.

Update the window after expansion​

The current window should represent the palindrome with the furthest known right endpoint. After calculating $P[i]$, compare $i+P[i]$ with $R$. If it is farther right, update $C$, $L$, and $R$.

Distinguish safe copying from verified expansion​

A copied radius is justified by symmetry only up to the current window edge. It should not be treated as proof beyond $R$. The clamp makes this distinction explicit and prevents the algorithm from skipping a necessary comparison.

Guard the transformed boundaries​

If an implementation does not use sentinels, the expansion loop must check that both candidate positions remain inside the transformed string. A comparison is valid only when both $i-P[i]-1$ and $i+P[i]+1$ are in range.

These details do not change the main algorithm, but they prevent the most common errors: off-by-one boundary mistakes, invalid mirror copies, and accidental confusion between transformed and original coordinates.

14. Complexity and storage​

For an input string of length $n$, the separator transformation creates a string whose length is linear in $n$. Manacher’s scan processes that transformed string in:

time overall.

The reason is the amortized boundary argument: the right edge moves right only a linear number of times, and the algorithm performs a linear amount of centre-level bookkeeping.

A standard implementation stores the transformed representation and one radius value per transformed centre. Both arrays have linear size, so the usual auxiliary storage is:

The exact constant depends on how separators, boundaries, and radius values are represented. The asymptotic result is unchanged by those representation details.

The trade-off is straightforward. The algorithm is more involved than independently expanding around every centre, because it must maintain a window, calculate mirrors, clamp radii, and update boundaries correctly. In return, it avoids repeated expansion and provides linear total running time.

The useful comparison is therefore between simplicity and asymptotic efficiency. Direct centre expansion is easy to describe and may be adequate for a small input or a one-off demonstration. Manacher’s algorithm requires more careful invariants, but it is designed for a complete palindrome-radius computation in linear time.

15. Common mistakes​

Mistake one: treating only characters as centres​

That misses even-length palindromes. The centre of abba is a gap, not a character. Interleaving separators gives that gap an explicit transformed position.

Mistake two: copying the entire mirror radius​

The mirror radius may extend beyond the current right boundary when reflected. The safe initialization is:

not simply $P[mirror]$.

Mistake three: assuming a copied radius needs no possible expansion​

When the copied radius reaches the boundary, the text beyond the boundary has not yet been checked. The algorithm must attempt expansion there.

Mistake four: updating the window for every palindrome​

Only a palindrome that reaches farther right improves the information available to future centres. A palindrome ending inside the current $R$ does not replace the rightmost window.

Mistake five: judging complexity from indentation​

The expansion loop is nested syntactically, but successful expansion advances the global right boundary. That shared progress is why the total cost is $O(n)$ rather than $O(n^2)$.

Mistake six: mixing coordinate systems​

The transformed string has separator positions that do not correspond directly to input characters. A radius or boundary calculated in transformed coordinates should not be interpreted as an original-string index without the appropriate conversion.

Mistake seven: changing the radius definition halfway through​

If one formula treats $P[i]$ as a count of successful comparisons while another treats it as a palindrome length, the mirror and boundary calculations will disagree. Define the convention once and use it everywhere.

16. The central idea in one sentence​

Manacher’s algorithm says: when a new centre lies inside a previously verified palindrome, first reflect it to its mirror, reuse the mirror’s known radius as far as the current right boundary allows, and perform fresh expansion only beyond that boundary.

The seven-character example makes all pieces visible:

original:    abacaba
transformed: #a#b#a#c#a#b#a#

The separators turn character centres and gap centres into the same kind of position. The radius array records how far each position can expand. The current window identifies the palindrome reaching furthest right. The mirror supplies already-known structure. The clamp prevents the algorithm from trusting symmetry outside the verified window. Finally, the global right boundary gives the expansion loop its linear amortized cost.

The phrase let the mirror answer does not mean that every centre receives its complete answer by copying. It means that copying is the first option whenever the centre lies inside a known palindrome. If the mirrored information reaches the known boundary, the algorithm asks the text for more evidence through fresh comparisons.

That distinction is the heart of the method. Manacher’s algorithm is not merely a palindrome routine with a clever formula. It is an example of disciplined reuse: preserve a verified region, reflect previously computed information into it, and spend new work only where the existing proof ends.

17. Practical takeaways​

When implementing or explaining Manacher’s algorithm, keep these questions in order:

1. What is the transformed string? Insert separators so odd and even palindromes share one centre-based representation.
2. What does the radius mean? Define it precisely before writing the boundary formulas.
3. What is the current window? Track the palindrome with the greatest known right endpoint.
4. Where is the mirror? For centre $i$, use $mirror=2C-i$, or equivalently $mirror=L+R-i$.
5. How much can be copied safely? Use the smaller of the mirror radius and the distance to the right edge.
6. What still needs verification? Expand only beyond the copied radius, especially when it reaches $R$.
7. Why is the total linear? Every successful fresh expansion advances the global right boundary, and every centre contributes only bounded stopping work.

This is the practical meaning of the title: the algorithm lets a mirror answer whenever an earlier palindrome has already proved the relevant symmetry. It does not eliminate every comparison. Instead, it ensures that comparisons are made only when they can extend the known boundary or finish the current centre. That disciplined reuse of structure is what turns palindrome expansion into one linear pass.