3.8.9 · D5String Algorithms
Question bank — Palindrome algorithms — Manacher's algorithm
Before you start, recall the five names you must never confuse:
- — the center of the rightmost-reaching palindrome found so far.
- — the right boundary of that palindrome (the "wall"): everything up to is symmetric about , nothing past is guaranteed.
- — the position we are currently solving for.
- — the mirror of across (its "buddy" on the other side).
- — the radius (in the padded string ) of the longest palindrome centered at .
The picture below fixes all five in one glance — refer back to it whenever a question mentions the wall or the mirror.
True or false — justify
TF1. "After the # transform, some palindromes in still have even length."
False — every palindrome in has odd length, because characters and
# strictly alternate so any palindrome's center is a single position, giving a symmetric shape wide.TF2. " (the radius in ) equals the length of the real palindrome in ."
True — a radius- palindrome in spans positions of which exactly are real characters, so the original length is precisely .
TF3. "Inside the known palindrome, is always exactly ."
False — it is exactly only when the mirror palindrome fits strictly inside the wall; if it touches or crosses the wall we know only and must expand.
TF4. "Once we set , the value can later decrease."
False — is monotonically non-decreasing; we update it only when , i.e. strictly rightward, which is exactly why the algorithm is .
TF5. "The expand loop can run times for a single index ."
True for one index in isolation, but each expansion step pushes forward by one, and never retreats, so across the whole sweep the total expansion work is — this "charge each unit of work to a boundary that only moves forward" argument is exactly Amortized Analysis.
TF6. "Manacher gives the answer for every center, not just the single longest palindrome."
True — the array holds a value for each of the centers, so counting all palindromic substrings or finding the longest are both one pass over .
TF7. "Expand-Around-Center and Manacher are equally fast in the worst case."
False — Expand Around Center, the simpler cousin that re-measures each center from scratch, is (a string of identical letters forces full re-expansion each time); Manacher reuses mirror answers to stay .
TF8. "If we can still copy from a mirror."
False — when sits at or past the wall there is no surrounding known palindrome to reflect through, so must start at and expand from scratch.
TF9. "The mirror index is always a valid (non-negative) index whenever ."
True — if then lies inside , so its reflection lies in the same interval, which is within the string bounds.
Spot the error
SE1. Someone writes P[i] = P[2*C - i] with no cap. Why is this wrong?
The mirror palindrome may stick out past the left edge of the big palindrome, where symmetry gives no guarantee; you must cap with and then expand.
SE2. Someone writes start = k - P[k] to map the best -index back to . Fix it.
It must be
(k - P[k]) // 2, because is roughly twice as dense (a # between every pair), so a -offset must be halved to become an -offset.SE3. The expand loop is while t[i-P[i]-1] == t[i+P[i]+1]: with no bound check. What breaks?
At the string ends this indexes out of range; you need
i-P[i]-1 >= 0 and i+P[i]+1 < m (recall is the length of ) even though the # padding softens the boundary.SE4. Someone uses the wall as R-i-1 instead of R-i in the cap. What goes wrong?
An off-by-one that under-trusts the mirror by one character, forcing an unnecessary expansion step and possibly a wrong (too-short) copy at the boundary — the correct cap is exactly .
SE5. Someone updates C,R = i, i+P[i] unconditionally every iteration. Why is that a bug?
You must update only when
i+P[i] > R; otherwise you can move the center to a smaller palindrome and shrink the reach, destroying the invariant that is the rightmost reach.SE6. Someone reflects with i' = C - (i - C) and thinks it differs from 2C - i.
They are identical: ; the "distance from " phrasing and the algebraic form are the same mirror.
SE7. Someone builds as '#'.join(s) (no leading/trailing #). What fails?
The first and last real characters lose a
# neighbour, so palindromes at the ends can't expand symmetrically and boundary radii come out wrong; you need '#' + '#'.join(s) + '#'.Why questions
WHY1. Why does the # trick unify odd and even palindromes?
An even palindrome of becomes an odd palindrome centered on a
# in , and an odd one centers on a real char — so in there is only one case (odd) to handle.WHY2. Why is the recurrence a and not just ?
We trust the mirror only as far as the wall reaches; takes the mirror's promise but clips it at where our symmetry knowledge ends.
WHY3. Why, in Case A (mirror fits strictly inside), can we be certain no expansion helps?
If could grow, symmetry would force its mirror to grow too — but is already maximal, a contradiction, so exactly.
WHY4. Why, in Case B (mirror hits/crosses the wall), must we expand character by character?
Beyond the two sides of are not guaranteed equal, so the mirror's extra length is unverified; only real comparisons past can confirm it.
WHY5. Why does amortization make the total expansion despite one index possibly expanding a lot?
Every successful expansion step advances by one and only increases, so the sum of all expansion steps is bounded by 's total travel — this "pay per unit of forward progress" accounting is the heart of Amortized Analysis.
WHY6. Why does the number of palindromic substrings centered at equal ?
Each real-palindrome layer corresponds to one odd radius value in ; counting those layers up to gives the ceiling of half the radius.
WHY7. Why does Manacher relate conceptually to the Z-Algorithm and KMP failure function?
All three maintain a "farthest useful boundary" and reuse previously computed structure instead of recomputing — the Z-Algorithm's Z-box and KMP failure function's borders play the same role as Manacher's wall .
WHY8. Why prefer Manacher over a Palindromic Tree (Eertree) for just the Longest Palindromic Substring?
Manacher is a tiny array-only pass with no tree structure; the Palindromic Tree (Eertree) pays to store every distinct palindrome, richer information you don't need when the goal is only the single Longest Palindromic Substring.
Edge cases
EC1. What does Manacher return for the empty string s = ""?
"#" (length 1), the single center has , so there are no palindromes and the longest is the empty string.EC2. What is for a single character s = "a"?
"#a#"; the center on a tries to expand but its two neighbours are the outer # and #, which match, giving radius — correctly recovering the length-1 palindrome a.EC3. On an all-same string like s="aaaa", why doesn't every index trigger a big expansion?
The mirror predicts most radii from within the ever-growing palindrome, so expansion fires only when it can push past the previous maximum — total expansions stay .
EC4. On a string with no repeats, e.g. s="abcde", what does look like?
Only single characters are palindromes, so real-char centers get and
# centers get ; the longest palindrome has length 1.EC5. At the very first index (a #), why is there no mirror step?
Initially , so is false; there is no known palindrome to reflect through, and starts at .
EC6. What happens at an index exactly at the wall, ?
The condition fails, so we do not copy a mirror value; we start from and expand, then possibly move the wall forward.
EC7. When two different centers give the same maximal , which does longest_pal return?
max(..., key=...) returns the first index achieving the maximum, so it returns the earliest-occurring longest palindrome — ties are broken by position, not arbitrarily.Recall One-line self-test before moving on
"Mirror, then push the Wall." If you can state why the min appears and why only moves right, you own the algorithm. Why the min? ::: Trust the mirror, but never past the wall where symmetry is unverified. Why is it ? ::: Expansion only advances the monotone boundary , so total work is bounded by 's forward travel.