Manacher's algorithm finds every palindromic substring of a string in O(n) time. The trick: interleave the string with a sentinel (say #) so odd- and even-length palindromes both become odd; then track a rightmost [C, R] palindrome and mirror already-computed radii into new ones. Watch each center as it's decided.
Each column's small dashed cell is p[i] — the palindrome radius around that center in the transformed string. The palindrome length in the original string is exactly p[i].
A palindrome centered on a single char (odd) has a different structure than one centered between two chars (even). Manacher unifies them by first transforming abba into #a#b#b#a#: now every center is a character in the transformed string, and the palindrome radius p[i] around center i equals the palindrome length in the original.
Maintain C and R: the center and right edge of the rightmost palindrome discovered so far. For each new index i:
i < R: the mirror of i across C is mirror = 2C − i. Copy p[i] = min(p[mirror], R − i) — a free lower bound.T[i − p[i] − 1] === T[i + p[i] + 1].i + p[i] > R: update C = i, R = i + p[i] — the window pushed right.
The right edge R only moves forward, and every char comparison after the copy either extends R or fails once — so total work is O(n). That's exponentially faster than the "check every center" quadratic and asymptotically optimal for the longest-palindromic-substring problem. Manacher's result also feeds into palindromic-tree constructions and eertree suffix links.