Manacher's Algorithm

Quick Revisit

• USE WHEN: Finding all maximal palindromic substrings or longest palindromic substring faster than expand-from-center
• INVARIANT: Maintain rightmost palindrome boundary; reuse mirror radii for positions inside it
• TIME: O(n) | SPACE: O(n)
• CLASSIC BUG: Forgetting the sentinel characters between chars (e.g., #a#b#a#) to unify odd/even length palindromes
• PRACTICE: 07-ladder-strings

Find all maximal palindromic substrings in $O(n)$. Solves "longest palindromic substring" optimally -- the go-to when expand-from-center is too slow.

Difficulty: [Intermediate]Prerequisites: Arrays and Strings. String hashing is not required -- Manacher rests on palindrome expansion and array indexing alone. Hashing is a useful follow-up for distinct-palindrome problems, not a prerequisite. CF Rating Range: 1600-2100

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

String $s = $ "abacaba" (length 7). Find the longest palindrome centered at each position.

The naive approach: for every center $i$, expand outward while characters match.

  s:  a   b   a   c   a   b   a
      0   1   2   3   4   5   6

  Center 0: "a"                           expand 0 times
  Center 1: "b" -> "aba"                  expand 1 time, check 1 pair
  Center 2: "a" -> "bab" -> "abacaba"?    expand 2 times, fail at pair 3
  Center 3: "c" -> "aca" -> "bacab"       expand 2 times, check 2+1 pairs
            -> "abacaba"                   expand 3 times, check 3+2+1 pairs
  Center 4: "a" -> "bab" -> "abacaba"?    expand 2 times, fail at pair 3
  Center 5: "b" -> "aba"                  expand 1 time
  Center 6: "a"                           expand 0 times
  ---------------------------------------------------------
  Total character comparisons: 0+1+2+3+3+2+1+0 = 12

That looks fine for 7 characters, but consider $s = $ "aaaaaa...a" ($n$ copies of 'a'). The palindrome centered at $n/2$ has radius $n/2$, so expansion alone costs $O(n)$ at that center. Summed over all centers: $O(n^2)$.

We're re-expanding regions we've already proven are palindromic. There has to be a better way.

If you're inside a known palindrome, the mirror position's radius gives you a free head start -- you only expand beyond what the mirror already guarantees.

Analogy: Imagine standing in a hallway with a mirror at the far wall. Everything you see to your left is reflected on the right -- you don't need to walk over and check, you already know what's there. In Manacher's algorithm, the "hallway" is the rightmost known palindrome, the "mirror" is its center, and the "reflection" copies a previously computed palindrome radius to a new position for free. You only walk further (expand) if you've reached the edge of the mirror's view.

The analogy breaks when the reflected palindrome extends beyond the hallway wall (i.e., the mirror value reaches past the right boundary). In that case, you can only guarantee what's inside the hallway -- you must physically check beyond it.

Visual Walkthrough

We compute the palindrome radius array $p[]$ for $s = $ "abacaba". $p[i]$ = max radius of palindrome centered at $i$ (number of characters on each side, so the palindrome length is $2\cdot p[i]+1$).

We maintain the rightmost palindrome boundary: center $c$, right edge $r=c+p[c]$.

  Initial: c = 0, r = 0, p = [0, 0, 0, 0, 0, 0, 0]

Step 1: $i=0$$i\ge r$ (0 >= 0), so no mirror info. Expand from radius 0. $s[-1]$ is out of bounds -- stop. $p[0]=0$. Update $c=0,r=0$.

  s:    a   b   a   c   a   b   a
  p:   [0]  .   .   .   .   .   .
        ^
        c,r

Step 2: $i=1$$i\ge r$. Expand: $s[0]$ vs $s[2]$ = 'a' vs 'a' -- match. $s[-1]$ vs $s[3]$ -- out of bounds, stop. $p[1]=1$. Update $c=1,r=2$.

  s:    a   b   a   c   a   b   a
  p:   [0] [1]  .   .   .   .   .
            c-------r

Step 3: $i=2$$i<r$ (2 < 2 is false). No mirror info. Expand: $s[1]$ vs $s[3]$ = 'b' vs 'c' -- mismatch. $p[2]=0$. No update ($i+p[i]=2\le r=2$).

  s:    a   b   a   c   a   b   a
  p:   [0] [1] [0]  .   .   .   .
            c-------r

Step 4: $i=3$$i\ge r$. Expand: $s[2]$ vs $s[4]$ = 'a' vs 'a' -- match. $s[1]$ vs $s[5]$ = 'b' vs 'b' -- match. $s[0]$ vs $s[6]$ = 'a' vs 'a' -- match. $s[-1]$ vs $s[7]$ -- out of bounds, stop. $p[3]=3$. Update $c=3,r=6$.

  s:    a   b   a   c   a   b   a
  p:   [0] [1] [0] [3]  .   .   .
                    c-----------r

Step 5: $i=4$$i<r$ (4 < 6). Mirror of $i$ around $c=3$: $mirror=2c-i=2$. $p[mirror]=p[2]=0$. Head start: $p[4]=min(p[2],r-i)=min(0,2)=0$. Expand: $s[3]$ vs $s[5]$ = 'c' vs 'b' -- mismatch. $p[4]=0$. No update.

  s:    a   b   a   c   a   b   a
  p:   [0] [1] [0] [3] [0]  .   .
                    c-----------r
        mirror <--- c ---> i
          (2)      (3)    (4)

Step 6: $i=5$$i<r$ (5 < 6). $mirror=2\cdot 3-5=1$. $p[mirror]=p[1]=1$. Head start: $p[5]=min(1,6-5)=1$. Expand from radius 1: $s[3]$ vs $s[7]$ -- out of bounds, stop. $p[5]=1$. Update $c=5,r=6$.

  s:    a   b   a   c   a   b   a
  p:   [0] [1] [0] [3] [0] [1]  .
                            c---r

Step 7: $i=6$$i\ge r$ (6 >= 6). Expand: $s[5]$ vs $s[7]$ -- out of bounds, stop. $p[6]=0$.

  s:    a   b   a   c   a   b   a
  p:   [0] [1] [0] [3] [0] [1] [0]

  Longest palindrome: center 3, radius 3 -> "abacaba" (length 7)

Brute force: 12+ comparisons. Manacher: 7 comparisons total (3 at center 3, 1 each at centers 1, 2, 4, 5, plus the boundary checks). On all-same strings the savings are dramatic: $O(n)$ vs $O(n^2)$.

From odd centers to the #-transformed version

The walkthrough above only handled odd-length palindromes -- every center sat exactly on a character. That is enough to get the idea, but "abba" has no single character at its midpoint, so the same loop misses every even-length palindrome.

Two equivalent fixes, both worth knowing:

1. Two passes. Run Manacher twice: once with centers on each character (odd palindromes, radius array $p_1$), and once with centers in each gap between characters (even palindromes, radius array $p_2$). Same algorithm, two arrays.

2. The #-transformation. Insert a fresh sentinel between every pair of characters and at both ends: "abba" becomes "#a#b#b#a#". Now every palindrome of the original -- odd or even -- becomes an odd-length palindrome in the transformed string. The algorithm stays exactly the loop you saw above; you just run it on the longer string.

   The mapping back is mechanical:

     original index k        ->  transformed index 2k + 1
     gap between k and k+1   ->  transformed index 2k + 2
     palindrome at trans. i with radius p[i]
        ->  original start = (i - p[i]) / 2
        ->  original length = p[i]

   So "#a#b#b#a#" with radius 4 at the middle # gives original start (4 - 4) / 2 = 0 and length 4 -- exactly "abba".

The implementation below uses the #-transformation because it lets the loop stay identical to the odd-only version. The two-pass variant is simpler to reason about but spreads the bookkeeping across two arrays. Pick the one whose bugs you can debug in a contest.

The Invariant

+-------------------------------------------------------------------+
| INVARIANT: Maintain the rightmost palindrome [c, c+p[c]].         |
| For new center i:                                                 |
|   p[i] >= min(p[2*c - i], right - i)   when i < right            |
| Expand only beyond this guaranteed bound.                         |
| The right boundary r never decreases -> amortized O(n).           |
+-------------------------------------------------------------------+

Why $O(n)$ amortized: every successful character comparison pushes $r$ to the right by 1. Since $r$ only increases and is bounded by $n$, the total number of successful expansions across all centers is at most $n$. Failed expansions cost $O(1)$ per center. So total work is $O(n)$.

  Amortized O(n) -- the right boundary r only moves right:

  Step:  0   1   2   3   4   5   6   7   8   9  10  11  12
  r:     0   0   2   2   2   6   6   6   6   6   6   6   6
         ─   ─   ╱   ─   ─   ╱   ─   ─   ─   ─   ─   ─   ─
              expand     expand
              +2         +4

  Total r advancement <= n  ->  total expansions <= n
  Mirror reuse steps:  O(1) each, no r advancement
  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  Grand total work: O(n)

Look at Step 5 above -- $p[mirror]=0$ and $r-i=2$. The head start is $min(0,2)=0$. Now imagine if $p[mirror]$ were 3 (larger than $r-i=2$). We'd cap at $r-i=2$ because the mirror palindrome extends beyond the known region -- we can't trust what's outside the right boundary. That cap is what prevents overcounting and keeps the invariant safe.

What the Code Won't Teach You

Counting palindromic substrings from $p[]$. Every center $i$ with radius $p[i]$ contributes palindromes of all valid radii from 1 to $p[i]$. In the #-transformed string, center $i$ contributes $\lceil p[i]/2\rceil$ palindromes. The total count is a single sum over the array -- but the code only computes $p[]$, not the count. You have to know the counting formula yourself.

$O(1)$ palindrome queries after Manacher. "Is $s[l..r]$ a palindrome?" reduces to checking whether the palindrome radius at the center of $[l,r]$ is large enough. In the transformed string: center index = $l+r+1$, required radius $\ge r-l+1$. This index mapping is the fiddly part the code doesn't explain, and getting it off-by-one turns correct preprocessing into wrong answers.

The eertree picks up where Manacher stops. Manacher gives palindrome radii at positions. The palindromic tree (eertree) gives distinct palindromes as objects with occurrence counts. For problems that say "count distinct palindromic substrings" or "DP over palindromes," Manacher alone isn't enough -- you need the eertree or a combination with hashing.

The mental model: Manacher is two-pointer, not DP. Beginners sometimes try to understand Manacher as some kind of dynamic programming. It's not. It's a two-pointer / sliding window idea in disguise. The right boundary $r$ only moves forward, and you're maintaining an invariant about the "known region" $[l,r]$. Each new center either gets a free answer from the mirror (no work) or extends $r$ rightward (amortized $O(1)$). Once you see it as "we're sweeping $r$ rightward and never going back," the linear time becomes obvious and the algorithm stops feeling magical.

The #-transformation is clever but error-prone. Inserting sentinel characters (#a#b#a#) to unify odd and even-length palindromes is elegant in theory but a source of off-by-one bugs in practice. The mapping between original indices and transformed indices is: original position $i$ maps to transformed position $2i+1$, and a palindrome of radius $r$ in the transformed string corresponds to a palindrome of length $r$ in the original. Many experienced competitors skip the transformation entirely and instead run Manacher twice -- once for odd-length, once for even-length centers -- because the bookkeeping is simpler even if the code is slightly longer.

Manacher is a building block, not a solution. By itself, Manacher just fills an array. The real work is what you do with that array. Need the longest palindrome? Scan for the max. Need to count all palindromic substrings? Sum $\lceil p[i]/2\rceil$. Need to check if every substring of length $k$ contains a palindrome? That's a sweep-line problem on the radius array. The algorithm is trivial to implement once memorized; the skill is recognizing which downstream computation your problem actually needs.

When to Reach for This

Trigger phrases:

• "longest palindromic substring" -> Manacher
• "count palindromic substrings" -> Manacher (count from $p[]$ array)
• "palindrome radius array" -> literally Manacher
• "all maximal palindromes" -> Manacher
• "palindromic substring in $O(n)$" -> Manacher

Counter-examples:

• "longest palindromic subsequence" -> This is DP ($O(n^2)$), not Manacher. Subsequences can skip characters; Manacher only handles contiguous substrings.
• "minimum insertions to make palindrome" -> Also DP on subsequences. See 05-dp-interval.md.
• "check if a single string is a palindrome" -> Just use two pointers. Manacher is overkill for a single check.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
string::operator[]	<string>	Random access to characters	$O(1)$
string::size()	<string>	Length of string	$O(1)$
min(a, b)	<algorithm>	Returns the smaller value	$O(1)$
max_element(first, last)	<algorithm>	Iterator to max in range	$O(n)$
vector<int>	<vector>	Stores $p[]$ radius array	$O(n)$ construct
string(count, char)	<string>	Build transformed string with separators	$O(n)$

Manacher uses no exotic STL -- it's a from-scratch algorithm on a character array.

---

Implementation (Contest-Ready)

4a. Odd-Length Palindromes Only (Minimal)

Computes $p[i]$ = max radius of odd-length palindrome centered at $i$.

#include <bits/stdc++.h>
using namespace std;

vector<int> manacher_odd(const string &s) {
    int n = s.size();
    vector<int> p(n, 0);
    int c = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (i < r) p[i] = min(p[2 * c - i], r - i);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && s[i - p[i] - 1] == s[i + p[i] + 1])
            p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
    }
    return p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    auto p = manacher_odd(s);
    int best = 0, center = 0;
    for (int i = 0; i < (int)s.size(); i++)
        if (p[i] > best) { best = p[i]; center = i; }
    cout << s.substr(center - best, 2 * best + 1) << "\n";
}

4b. Full Manacher -- Odd + Even via Separator Trick (Minimal)

Insert a sentinel # between every pair of characters (and at both ends) so that every palindrome -- odd or even -- becomes odd-length in the transformed string.

#include <bits/stdc++.h>
using namespace std;

vector<int> manacher(const string &s) {
    // Transform: "abc" -> "#a#b#c#"
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();
    vector<int> p(n, 0);
    int c = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (i < r) p[i] = min(p[2 * c - i], r - i);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1])
            p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
    }
    return p; // p[i] in transformed string = palindrome length in original
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    auto p = manacher(s);
    int best = 0, center = 0;
    for (int i = 0; i < (int)p.size(); i++)
        if (p[i] > best) { best = p[i]; center = i; }
    // Convert back: original start = (center - best) / 2, length = best
    cout << s.substr((center - best) / 2, best) << "\n";
}

4c. Full Manacher (Explained)

#include <bits/stdc++.h>
using namespace std;

vector<int> manacher(const string &s) {
    // Transform: insert '#' between every character and at both ends.
    // "abba" -> "#a#b#b#a#"
    // This unifies odd and even palindromes: an even palindrome "abba"
    // becomes the odd palindrome "#a#b#b#a#" centered at the middle '#'.
    // After the algorithm, p[i] in the transformed string equals the
    // length of the corresponding palindrome in the original string.
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();
    vector<int> p(n, 0);

    // c = center of the palindrome with the rightmost boundary
    // r = that rightmost boundary (c + p[c])
    int c = 0, r = 0;

    for (int i = 0; i < n; i++) {
        // Mirror position of i with respect to center c.
        int mirror = 2 * c - i;

        // If i is within the rightmost palindrome [c-p[c], c+p[c]],
        // we can reuse the mirror's radius as a lower bound.
        // But we can't exceed r - i (distance to the right boundary),
        // because beyond r we have no information.
        if (i < r)
            p[i] = min(p[mirror], r - i);

        // Expand beyond the guaranteed region.
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1])
            p[i]++;

        // If this palindrome extends past the current rightmost boundary,
        // update c and r. This is what drives the amortized O(n) bound:
        // r only increases.
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
    }
    return p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    auto p = manacher(s);

    // Find longest palindromic substring.
    int best = 0, center = 0;
    for (int i = 0; i < (int)p.size(); i++) {
        if (p[i] > best) {
            best = p[i];
            center = i;
        }
    }

    // Convert transformed coordinates back to original:
    // Original start index = (center - best) / 2
    // Original length = best  (because p[i] in '#'-string = original length)
    int start = (center - best) / 2;
    cout << s.substr(start, best) << "\n";
}

---

Operations Reference

Once the $p[]$ array is built, most palindrome queries reduce to simple arithmetic on its values.

Operation	Time	Space
Build palindrome radius array $p[]$	$O(n)$	$O(n)$
Longest palindromic substring	$O(n)$	$O(n)$
Count total palindromic substrings	$O(n)$	$O(n)$
Check if substring $s[l..r]$ is palindrome (with $p[]$)	$O(1)$	$O(n)$ preprocess
Count distinct palindromic substrings	$O(n)$ with eertree; $O(n\log n)$ with Manacher + hashing	$O(n)$

---

Problem Patterns & Tricks

Pattern 1: Longest Palindromic Substring

The classic application. Run Manacher, find $max(p[i])$, extract the substring.

auto p = manacher(s);
int best = *max_element(p.begin(), p.end());

Problems: CF 1326D2, CSES Longest Palindrome

Pattern 2: Count All Palindromic Substrings

Each center $i$ in the original string contributes $\lfloor (p[i]+1)/2\rfloor$ odd-length palindromes (if you run the odd-only version). With the #-transformed version, center $i$ contributes $\lceil p[i]/2\rceil$ palindromes.

auto p = manacher(s);
long long count = 0;
// In the transformed string "#a#b#a#", p[i] directly gives count contributions
for (int i = 0; i < (int)p.size(); i++)
    count += (p[i] + 1) / 2; // ceil(p[i] / 2) for '#' centers, floor for char centers

Problems: CF 17E, CF 1081H

Pattern 3: Palindrome Partitioning Preprocessing

Many DP problems need "is $s[l..r]$ a palindrome?" as a subroutine. Precompute $p[]$ with Manacher, then answer each query in $O(1)$: $s[l..r]$ is a palindrome iff the center $(l+r)/2$ has $p[\text{center}]\ge (r-l)/2$ (using appropriate transformed indices).

Problems: CF 1808E

  Original <-> Transformed index mapping:

  Original:     a     b     b     a
  Index:        0     1     2     3

  Transformed:  #  a  #  b  #  b  #  a  #
  Index:        0  1  2  3  4  5  6  7  8

  Char at original index k  ->  transformed index 2k + 1
  Gap between original k, k+1  ->  transformed index 2k + 2

  Palindrome centered at transformed i with radius p[i]:
    Original start = (i - p[i]) / 2
    Original length = p[i]

  Example: "abba" centered at transformed 4 (#), p[4] = 4
    start = (4 - 4) / 2 = 0,  length = 4  ->  "abba" OK

Pattern 4: Shortest Palindrome / Palindromic Prefix

Find the longest palindromic prefix of $s$ -- equivalently, the shortest string to prepend to make $s$ a palindrome. Run Manacher and find the largest $p[i]$ such that the palindrome starts at index 0.

auto p = manacher(s);
// In transformed string "#a#b#...", a palindromic prefix of the original string
// has its palindrome touching the very start of the transformed string: i - p[i] == 0
int longest_prefix_pal = 0;
for (int i = 0; i < (int)p.size(); i++)
    if (i - p[i] == 0) // palindrome touches left boundary of transformed string
        longest_prefix_pal = max(longest_prefix_pal, p[i]);

Problems: CF 1326D2

Pattern 5: Manacher + Hashing Combo

For problems requiring distinct palindromic substrings or palindrome matching, combine Manacher's $p[]$ with string hashing. Manacher identifies all maximal palindromes in $O(n)$; hashing deduplicates or matches them.

Problems: CF 7D

Pattern 6: Even-Only or Odd-Only Palindromes

Some problems restrict to even-length or odd-length palindromes. Instead of the full #-transformation, run the odd-only version twice -- once on the original (for odd palindromes) and once on the "gap" positions (for even). Or use the transformed version and filter by whether the center index is odd or even in the #-string.

Problems: CF 1081H

---

Contest Cheat Sheet

+----------------------------------------------------------------+
|               MANACHER'S ALGORITHM CHEAT SHEET                  |
+----------------------------------------------------------------+
| WHEN TO USE:                                                    |
|   o Longest palindromic substring in O(n)                       |
|   o Count all palindromic substrings                            |
|   o Palindrome radius array for DP preprocessing                |
|   o Any problem where expand-from-center is TLE                 |
+----------------------------------------------------------------+
| TRANSFORM (odd+even unified):                                   |
|   "#a#b#c#"  ->  every palindrome becomes odd-length            |
|   p[i] in transformed = palindrome length in original           |
+----------------------------------------------------------------+
| CORE LOOP:                                                      |
|   c=0,r=0; for(i=0..n-1) {                                     |
|     if(i<r) p[i]=min(p[2*c-i], r-i);                           |
|     while(bounds_ok && t[i-p[i]-1]==t[i+p[i]+1]) p[i]++;       |
|     if(i+p[i]>r) c=i, r=i+p[i]; }                              |
+----------------------------------------------------------------+
| EXTRACT ANSWER:                                                 |
|   best = max(p[i]), start = (center - best) / 2, len = best    |
+----------------------------------------------------------------+
| COMPLEXITY: O(n) time | O(n) space                              |
+----------------------------------------------------------------+

---

Gotchas & Debugging

Off-by-one in boundary checks

• The expansion condition needs i - p[i] - 1 >= 0 and i + p[i] + 1 < n. Forgetting either causes out-of-bounds access. On some judges this silently gives WA instead of RE.

Forgetting the # transformation for even-length palindromes

• The odd-only version misses even-length palindromes entirely. "abba" has no single center character -- you need the #-transform or a separate even-length pass. Default to the full version in contests.

Converting back to original coordinates

• In the transformed string "#a#b#c#", character s[k] sits at transformed index $2k+1$. The original start of a palindrome centered at transformed index $i$ with radius $p[i]$ is $(i-p[i])/2$, and its length in the original string is $p[i]$.
• Getting this conversion wrong shifts your answer or gives wrong lengths.

Empty string or single character

• $n=0$: the transformed string is just "#". Guard accordingly.
• $n=1$: the answer is trivially the whole string. Manacher handles it, but be aware.

r initialization

• Initialize $c=0,r=0$ (not $r=-1$). With $r=0$, the condition i < r is false for $i=0$, which is correct -- there's no known palindrome to mirror from initially.

Debugging tip

• Print $p[]$ for the transformed string on a small input. Each # position's radius corresponds to an even-length palindrome; each letter position's radius corresponds to an odd-length palindrome. Verify a few by hand.

Mental Traps

Trap 1: "Manacher's is just brute-force center expansion with a cache."

The "cache" (mirror reuse) is the entire algorithm. Without it, you have $O(n^2)$ expand-from-center. With it, you have $O(n)$. The insight is that the right boundary $r$ can only advance -- every successful expansion pushes $r$ rightward, and $r$ is bounded by $n$. Mirror positions inside the known palindrome get their radii for free.

  Without Manacher (all-'a' string of length n):

  Center 0:  expand 0 times     ─
  Center 1:  expand 1 time      ──
  Center 2:  expand 2 times     ────
  ...
  Center n/2: expand n/2 times  ─────────────────
  Total: 0 + 1 + 2 + ... + n/2 = O(n²)

  With Manacher:
  Center 0:  expand 0, r stays  ─
  Center 1:  expand 1, r->2      ──
  Center 2:  mirror gives 0     (free)
  Center 3:  expand 3, r->6      ──────
  Center 4:  mirror gives 0     (free)
  Center 5:  mirror gives 1     (free)
  Center 6:  mirror gives 0     (free)
  Total r advancement: n. Total work: O(n).

Trap 2: "I can handle odd and even palindromes separately without the # transformation."

You can, but you'll write two separate passes with different center-handling logic and twice as many edge cases. The #-transformation unifies both into one pass where every palindrome -- odd or even -- becomes odd-length. The separate approach is where most implementation bugs live (forgetting the even case, off-by-one on gap centers). Default to the transformation in contests.

---

Common Mistakes

1. Sentinel-to-original radius conversion. "My Manacher implementation returned radius 3 for the string abc, claiming a length-7 palindrome exists..." You used the sentinel trick (#a#b#c#) but forgot to divide the radius by 2 when converting back to the original string's coordinates. In the transformed string, a radius of 3 at a # position means an even-length palindrome of length 2 in the original. Always convert: original length = radius (in the sentinel string), and original start = (center - radius) / 2.

Debug Drills

Drill 1 -- Mirror initialization goes out of bounds

for (int i = 0; i < n; i++) {
    int mirror = 2 * c - i;
    d[i] = min(d[mirror], r - i);  // BUG when i > r
    // ... expand ...
}

What's wrong?

When i >= r, there's no valid mirror information. You must initialize d[i] = 0 (or 1 depending on convention) in that case:

if (i < r)
    d[i] = min(d[2 * c - i], r - i);
else
    d[i] = 0;

Drill 2 -- Forgetting to update center and right

while (i + d[i] < n && i - d[i] >= 0 && s[i + d[i]] == s[i - d[i]])
    d[i]++;
// Missing: if (i + d[i] > r) { c = i; r = i + d[i]; }

What's wrong?

Without updating c and r, every position starts with d[i] = 0 (since i >= r is always true). The algorithm degrades to $O(n^2)$ expand-from-center. Add:

if (i + d[i] > r) {
    c = i;
    r = i + d[i];
}

Drill 3 -- Even-length palindromes missed

// Only computing odd-length palindromes
for (int i = 0; i < n; i++) {
    // ... Manacher for d1[i] (odd radii) ...
}
// Forgot d2 array entirely

What's wrong?

Manacher's algorithm needs to handle both odd-length and even-length palindromes. Either run the algorithm twice (once for d1 with odd centers, once for d2 with even centers between characters) or use the sentinel trick to unify both cases into a single pass.

---

Self-Test

Before moving to problems, verify you can do these without looking at the notes:

• [ ] Apply the # transformation to "abba", state the new length ($2\cdot 4+1=9$), and describe the index mapping between original and transformed positions
• [ ] Implement Manacher from memory: the $c,r$ window, mirror initialization p[i] = min(p[2c - i], r - i), naive expansion, and window update -- in the correct order
• [ ] Convert $p[i]$ in the transformed string to original palindrome length and start index, for both #-centered and letter-centered positions
• [ ] Explain in one sentence why Manacher is $O(n)$: the right boundary $r$ only increases, bounding total expansion work to $n$
• [ ] Solve "longest palindromic substring" end-to-end: build $p[]$, find $max(p[i])$, extract the substring from the original string

---

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Expand-from-center $O(n^2)$ approach for longest palindromic substring.
1500	Implement Manacher's algorithm (odd-length version); find the longest palindromic substring in $O(n)$.
1800	Handle both odd and even palindromes (sentinel insertion or two separate arrays); use Manacher radii for counting or DP.
2100	Combine Manacher with binary search, hashing, or segment trees for palindrome range queries.

#	Problem	Source	Difficulty	Key Idea
1	Longest Palindrome	CSES	Easy	Direct Manacher application
2	Longest Palindromic Substring	LeetCode 5	Easy	Classic Manacher
3	Palindromic Characteristics	CF 835D	1900	Manacher + counting palindrome properties
4	Prefix-Suffix Palindrome	CF 1326D2	1800	Longest palindromic prefix/suffix + greedy
5	Palindrome Degree	CF 7D	1900	Recursive palindrome property via Manacher
6	Palindrome Pairs	CF 17E	2400	Count palindromic substrings + combinatorics
7	Palindromic Matrix	CF 1081H	2600	Advanced Manacher + DP
8	Palindromes in a String	CF 1808E	2300	Manacher preprocessing for palindrome queries

---

Further Reading

• cp-algorithms: Manacher's Algorithm -- full derivation, both odd and even versions, complexity proof
• CF Blog: Manacher's Algorithm tutorial -- community walkthrough with visuals
• CF Blog: Palindromic tree (eertree) -- related structure for distinct palindromes

Related guidebook entries:

• String Hashing -- combine with Manacher for deduplication
• KMP and Z-Function -- similar "rightmost boundary" amortization trick
• Suffix Array -- alternative approach for some palindrome problems