Manacher's Algorithm

Strings O(n) O(n)

Finds the longest palindromic substring in linear time by expanding around centers and mirroring radii across the current palindrome.

transform

^·0

#·1

A·2

#·3

B·4

#·5

A·6

#·7

B·8

#·9

A·10

#·11

B·12

#·13

A·14

#·15

$·16

Text

i=0c=0r=0

1/39

Center c and right edge r start at 0.

Invariantp[i] is the radius of the palindrome centred at i. Inside the known window that radius is mirrored, so no character is compared twice.

pointermatchmismatchwindow

manacher.c

/* transform: "aba" -> "^#a#b#a#$" */
int manacher(const char *t, int n, int p[]) {
    int c = 0, r = 0, best = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i < r)
            p[i] = min(r - i, p[2 * c - i]);
        while (t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i]++;
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
        if (p[i] > best) best = p[i];
    }
    return best;
}

How Manacher's Algorithm works

Insert separators so every palindrome has odd length, then expand around each center — but first seed each radius from its mirror inside the current rightmost palindrome. Every character is expanded over at most once.

When to use it

Longest palindromic substring in O(n); palindrome counting and factorization.