1. The Problem

Find the length of the longest palindromic substring centered at every position in a string $$$S$$$ in $$$\mathcal{O}(N)$$$ time. The naive approach expands around each center, which takes $$$\mathcal{O}(N^2)$$$ time. E.g., for $$$S = \text{"aaaaa..."}$$$, every center expands all the way to the edges.

Manacher's optimizes this by exploiting the defining property of palindromes which is symmetry.

Imagine we have already discovered a palindrome that spans from index $$$l$$$ to index $$$r$$$.
If our current center $$$i$$$ is strictly inside this palindrome ($$$l \le i \le r$$$), the right side of the palindrome is an exact mirror image of the left side.

Because we process the string from left to right, we have already calculated the answer for the mirror index on the left side. Let's call that mirror index $$$j$$$. We can just copy the answer from $$$j$$$ to $$$i$$$ and skip all that redundant work.

2. Odd-Length Palindromes

Let $$$d_1[i]$$$ be the radius of the odd-length palindrome centered at $$$i$$$. For "aba", $$$d_1 = [1, 2, 1]$$$.

If we are at index $$$i$$$, how do we find its mirror $$$j$$$ across the center of our palindrome [l, r] ?
The distance from the left boundary to $$$j$$$ must equal the distance from $$$i$$$ to the right boundary $$$r$$$.

We can initially set $$$d_1[i] = d_1[j]$$$ but there is a catch.
What if the palindrome centered at $$$j$$$ is so big that its left edge spills outside our known boundary $$$l$$$ ?
The string is only guaranteed to be symmetric strictly inside $$$[l, r]$$$. We know absolutely nothing about the characters past $$$r$$$.

Because of this we have to cap our initial answer so it doesn't exceed $$$r$$$.

After this $$$\mathcal{O}(1)$$$ initialization, we just resume the naive while loop to check if the palindrome extends past $$$r$$$. If it does we update our $$$l$$$ and $$$r$$$ boundaries.

Why is it $$$\mathcal{O}(N)$$$ ?
Even though we have a while loop inside a for loop, the while loop only successfully matches characters that strictly exceed $$$r$$$. Every successful match pushes $$$r$$$ to the right. Since $$$r$$$ starts at 0 and can never exceed $$$N$$$, the inner loop does at most $$$N$$$ successful comparisons overall.

3. Even-Length Palindromes and the !z Trick

For even palindromes (like "abba") the center is floating between characters.

The standard trick is to insert dummy characters (e.g., #) between every letter so $$$S = \text{"abba"}$$$ becomes $$$T = \text{"#a#b#b#a#"}$$$. This forces all palindromes to be odd-length, so you only need one loop.

The problem is that this doubles your string length. That means $$$2 \times$$$ the memory allocations and a worse constant factor which may cause TLEs on some problems.

If we don't use #, we have to write a second array $$$d_2[i]$$$ (the half-length of the even palindrome centered between $$$i-1$$$ and $$$i$$$). Because the center is shifted to $$$i - 0.5$$$ the mirror math shifts by $$$+1$$$.

Writing two nearly identical for loops is not probably the best idea.
But notice the difference between the odd mirror ($$$l + r - i$$$) and the even mirror ($$$l + r - i + 1$$$).

Let z = 1 handle odd lengths, and z = 0 handle even lengths. Notice that the boolean negation !z evaluates to $$$0$$$ for odd and $$$1$$$ for even. We can use !z to perfectly handle the $$$+1$$$ shift and squish both loops into one block.

Here is a template that you can use. It computes the arrays in $$$\mathcal{O}(N)$$$ and then allows you to answer isPalindrome(l, r) queries in $$$\mathcal{O}(1)$$$.

struct Manacher {
    vector<int> p[2];
    Manacher(string s) {
        int n = s.size();
        p[0].resize(n + 1);
        p[1].resize(n);
        for (int z = 0; z < 2; z++) {
            for (int i = 0, l = 0, r = 0; i < n; i++) {
                int t = r - i + !z;
                if (i < r) p[z][i] = min(t, p[z][l + t]);
                int L = i - p[z][i], R = i + p[z][i] - !z;
                while (L >= 1 && R + 1 < n && s[L - 1] == s[R + 1]) {
                    p[z][i]++; 
                    L--; 
                    R++;
                }
                if (R > r) { l = L; r = R; }
            }
        }
    }
  
    bool isPalindrome(int l, int r) {
        int mid = (l + r + 1) / 2;
        int len = r - l + 1;
        return 2 * p[len % 2][mid] + len % 2 >= len;
    }
};

4. Online Manacher

What if the string isn't fully given to you in advance ?

Let's assume you are receiving a stream of characters and you need to maintain palindromes dynamically then we can adapt Manacher's to work completely online. Instead of iterating $$$i$$$ from $$$0$$$ to $$$N$$$, we only need to keep track of the Main Palindrome, the longest palindrome whose right boundary exactly touches the current end of the string. Let's call its center $$$C$$$.

When you append a new character $$$S[N]$$$, only two things can happen.
1. The Main Palindrome Expands: We look at the character immediately to the left of the Main Palindrome. If it matches $$$S[N]$$$, our palindrome just grew by 2 characters. We increase its radius, update the boundaries and we're done in $$$\mathcal{O}(1)$$$.
2. The Main Palindrome Breaks: If it doesn't match, we must search for a new Main Palindrome. We do this by moving the center $$$C$$$ forward (to the right). As we move it, we use the exact same mirror logic we derived earlier to instantly initialize the new centers. We keep advancing $$$C$$$ until we find a center that successfully expands to absorb $$$S[N]$$$.

In Case 2, we have to run a while loop to advance the center. But notice that the center pointer $$$C$$$ only ever moves to the right. It never goes backwards. Over the course of adding $$$N$$$ characters, $$$C$$$ can only increment a maximum of $$$N$$$ times. Therefore, the total work done across all appends is bounded by $$$N$$$, making the online insertion strictly amortized $$$\mathcal{O}(1)$$$ per character.