⚙️AlgorithmIntermediate

Manacher's Algorithm

Key Points

  • •
    Manacher's algorithm finds the length of the longest palindrome centered at every position in a string in linear time O(n).
  • •
    It maintains the rightmost-known palindrome and uses mirror symmetry to skip redundant character comparisons.
  • •
    You can handle odd and even palindromes either with two arrays (d1 for odd, d2 for even) or by inserting separators (e.g., '#') into a transformed string.
  • •
    The total number of palindromic substrings equals the sum of all odd and even radii: sum(d1) + sum(d2).
  • •
    The algorithm is optimal for counting palindromic substrings, finding the longest palindromic substring, and answering center-maximum queries.
  • •
    Careful index handling prevents off-by-one errors, especially for even-length centers and boundary mirroring.
  • •
    The core invariant is that each new expansion increases the right boundary at most n times, ensuring O(n) total work.
  • •
    Manacher's is a staple in competitive programming (CF 1600–2000) where O() palindromic checks would time out.

Prerequisites

  • →Strings and indexing — Understanding zero-based indexing and substring ranges is essential to manage palindrome centers and boundaries.
  • →Two-pointer technique — Center expansion is a symmetric two-pointer process that compares characters moving outward.
  • →Asymptotic complexity (Big-O) — To appreciate why Manacher’s is linear and when it outperforms quadratic methods.
  • →Arrays and prefix sums — The radii arrays d1 and d2 store per-index information; counts rely on summations over arrays.
  • →Basic algorithm invariants — Maintaining and updating the rightmost palindrome [L, R] relies on understanding loop invariants.
  • →Character comparison and bounds checking — Correct expansions depend on stopping at mismatches or boundaries without out-of-bounds access.
  • →Integer types and overflow — Counting palindromic substrings can reach Θ(n^2), so using 64-bit integers is necessary.

Detailed Explanation

Tap terms for definitions

01Overview

Manacher's algorithm is a linear-time method to find palindromes centered at every index of a string. A palindrome reads the same forwards and backwards, like "racecar" or "abba". Naively, you could expand around each center and compare characters outwards, which takes O(n^2) in the worst case. Manacher's key insight is to cache the longest palindrome seen so far and exploit symmetry about its center to initialize the search for new centers, dramatically reducing redundant checks.

There are two common presentations. The first keeps two arrays: d1[i] stores the radius of the longest odd-length palindrome centered at i, and d2[i] stores the radius for even-length palindromes centered between i−1 and i. The second transforms the string by inserting separator characters (e.g., '#') between letters so that every palindrome becomes "odd" in the transformed space, allowing a single array p to hold radii.

With these radii, you can quickly compute the longest palindromic substring, count all palindromic substrings, or answer queries like "what is the longest palindrome centered at i?" All of this runs in O(n) time and O(n) space, which is optimal for such center-based problems.

02Intuition & Analogies

Imagine you’re scanning a street of mirrors. You find a giant symmetric arch (a known palindrome) spanning houses from L to R, centered at C. Now, when you reach a new house i within that arch, you can look at the mirror image house k on the other side of the center: k = L + R − i. Whatever symmetry exists around k suggests how much symmetry also exists around i—up to the right boundary R of your known arch. So instead of starting from scratch at i, you already have a head start: a guaranteed minimum palindrome radius at i coming from its mirror.

However, the mirror’s information is only reliable as long as you stay within the big arch’s boundary. Past that, you actually have to check characters to the right. If you expand beyond R, great—you discovered a larger arch and update L and R. If not, you wasted no time: you only tried as far as the boundary suggested.

For odd-length palindromes, each house is a potential center, like the letter 'a' in "abacaba". For even-length palindromes, the centers are between houses (between letters), like the gap between 'a' and 'a' in "baab". You can treat these two kinds of centers separately (two arrays) or merge them by putting fences (#) between letters so every center is a character in the new string. The magic is that every actual character comparison either increases the global right boundary or is bounded by previously known info. Hence, linearly many useful comparisons happen overall, which is why the algorithm runs in O(n).

03Formal Definition

Let s be a string of length n indexed from 0 to n−1. Define two arrays: - d1[i]: the maximum integer r ≥ 1 such that the substring s[i−r+1..i+r−1] is a palindrome (odd length). The palindrome length is 2r−1. - d2[i]: the maximum integer r ≥ 0 such that the substring s[i−r..i+r−1] is a palindrome (even length). The palindrome length is 2r. Manacher’s algorithm maintains, for each parity (odd/even), a rightmost-known palindrome interval [L, R] and processes centers from left to right. At a new center i with mirror k = L + R − i, an initial radius r0 is set as r0 = min(d[k], R − i + 1) for odd, or r0 = min(d[k], R − i + 1) with parity-corrected indices for even. Then, it attempts to expand beyond r0 by comparing characters symmetrically around i until mismatch or bounds. If i plus the new radius minus one exceeds R, it updates [L, R]. This ensures each character contributes to expansions only when R increases, bounding the total number of character comparisons by O(n). Alternatively, define the transformed string T = "^#" + join each s[j] with "#" + "#$". For each position i in T (excluding sentinels), p[i] stores the maximum r ≥ 0 such that T[i−r..i+r] is a palindrome (always odd in T). Mirroring, initialization, and expansion follow similarly with center C and right boundary R in T.

04When to Use

Use Manacher’s algorithm when you need palindrome information at all centers in linear time. Common tasks include:

  • Finding the single longest palindromic substring in a large string where O(n^2) would be too slow.
  • Counting all palindromic substrings efficiently; this is exactly sum(d1) + sum(d2) in O(n).
  • Answering queries like "What is the length of the longest palindrome centered at index i?" in O(1) after preprocessing.
  • Precomputing radii for dynamic programming or string algorithms that need palindrome structure (e.g., minimum palindromic partitioning heuristics, near-palindrome checks).
  • Competitive programming problems where strings can be up to 2e5+ and multiple test cases require fast per-test linear preprocessing.

Prefer the two-array version (d1, d2) when you need direct access to odd/even radii in original indexing. Prefer the transformed-string version when a unified view simplifies code (single array p), especially when only the longest palindrome is required. If you only need to test whether a single substring is a palindrome, Manacher’s may be overkill; hashing (e.g., rolling hash) might be simpler. But if you need palindrome info for many centers or counts, Manacher’s is ideal.

⚠️Common Mistakes

  • Off-by-one errors in even centers: For d2, the palindrome is s[i−r .. i+r−1]; it is easy to accidentally shift by one and compare s[i−r−1] with s[i+r] incorrectly. Always re-derive the indices before coding.
  • Mixing definitions of radius: Some sources define d1[i] as the number of characters matched on one side (including center), others as a half-length. Be consistent: length_odd = 2⋅d1[i] − 1 and length_even = 2⋅d2[i].
  • Incorrect mirror index: The mirror of i is k = L + R − i for odd. For even, the [L, R] definition and mirror formula involve slightly different off-sets; copying the odd formula blindly can break correctness. Use a standard, tested template.
  • Forgetting to reset [L, R] for even pass: You need separate passes (and boundaries) for odd and even. Reusing odd’s [L, R] for even will yield wrong results.
  • Not handling empty strings or single-character strings: Initialize arrays and loops to gracefully handle n = 0 or n = 1.
  • Overflow in counts: The number of palindromic substrings can be Θ(n^2) in strings like "aaaa…a"; store counts in 64-bit integers (long long) even though the algorithm runs in O(n) time.
  • Transform-string pitfalls: Missing sentinels (like '^' and '$') or using the same separator as a possible input character can cause out-of-bounds or false matches. Choose separators not in the input alphabet and add guards.

Key Formulas

Odd-length radius

Explanation: If d1[i] equals r, the longest odd palindrome centered at i spans r characters to the left and right, counting the center once. The total length is 2r − 1.

Even-length radius

Explanation: If d2[i] equals r, the longest even palindrome is centered between i−1 and i and extends r characters each way. The total length is 2r.

Mirror index

Explanation: For a center i within the current rightmost palindrome [L, R], k is i's mirror across the center. Radii at k often bound radii at i by symmetry.

Initialization by symmetry (odd case)

Explanation: The initial radius at i is at least as large as the mirror’s radius but cannot extend beyond the known right boundary. This seeds expansion without redundant work.

Counting palindromes

Explanation: Each center contributes exactly d1[i] odd palindromes and d2[i] even palindromes. Summing over all centers yields the total count.

Transformed string

T = \hat{\ }\# s_0 \# s_1 \# \cdots \# s_{n-1} \# \
$

Explanation: Insert separators and sentinels so every palindrome in T is odd-length. This unifies handling of odd and even palindromes with a single radius array p.

Transformed length

Explanation: If T includes two sentinels and n separators between n characters, the total length is 2n + 3. Indices run from 0 to m − 1.

Recovering LPS from transformed string

Explanation: Given the best center and radius in T, divide by 2 (discarding separators) to map back to original indices. maxLen equals p[bestCenter].

Time and space complexity

Explanation: Manacher’s algorithm runs in linear time and uses linear extra space for radii arrays. This is asymptotically optimal for per-center palindrome information.

Amortized expansion bound

Explanation: Each successful expansion increases the global right boundary. Since the boundary can move right at most n − 1 times, total extra expansions are linear.

Complexity Analysis

Manacher’s algorithm achieves linear time by reusing information from the rightmost-known palindrome and restricting fresh comparisons to positions that potentially extend the global right boundary. In the odd-length pass, each center i initializes its radius using its mirror’s value and the current right boundary R: r0 = min(d1[k], R − i + 1). Only when attempting to expand beyond r0 are character comparisons performed. Critically, these expansions either fail immediately or succeed and increase R. The right boundary can increase at most n − 1 times overall, so the total number of successful character comparisons (those that advance R) across the entire pass is O(n). Unsuccessful constant-time checks are also bounded per index, giving O(n) time. The even-length pass mirrors this reasoning independently, resulting in O(n) for both passes combined. In the transformed-string variant, a single pass maintains a center C and right boundary R in the transformed space. The same amortized argument applies: p[i] initializes to min(p[mirror], R − i), and expansions only proceed when potentially increasing R. The total work is O(m) = O(n), since m = 2n + 3. Space complexity is O(n) for storing d1 and d2 or O(n) for p in the transformed approach. Additional memory includes the input string and a few integers for boundaries and centers—thus overall O(n) auxiliary space. Counting palindromes or extracting the longest palindrome requires no extra asymptotic space beyond these arrays. Even when computing both odd and even arrays and auxiliary outputs (e.g., counts, indices), the memory remains linear in n.

Code Examples

Compute d1 (odd) and d2 (even) radii and extract the Longest Palindromic Substring
1#include <bits/stdc++.h>
2using namespace std;
3
4// Manacher: compute odd and even radii.
5// d1[i]: max r >= 1 such that s[i - r + 1 .. i + r - 1] is palindrome (odd length)
6// d2[i]: max r >= 0 such that s[i - r .. i + r - 1] is palindrome (even length)
7struct Manacher {
8    vector<int> d1, d2; // odd and even radii
9    void build(const string &s) {
10        int n = (int)s.size();
11        d1.assign(n, 0);
12        int l = 0, r = -1;
13        // Odd-length palindromes
14        for (int i = 0; i < n; ++i) {
15            int k = 1;
16            if (i <= r) {
17                int mirror = l + r - i; // mirror index inside [l, r]
18                k = min(d1[mirror], r - i + 1);
19            }
20            // Try to expand around i
21            while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) ++k;
22            d1[i] = k;
23            // Update [l, r] if we extended further to the right
24            if (i + k - 1 > r) {
25                l = i - k + 1;
26                r = i + k - 1;
27            }
28        }
29        // Even-length palindromes
30        d2.assign(n, 0);
31        l = 0; r = -1;
32        for (int i = 0; i < n; ++i) {
33            int k = 0;
34            if (i <= r) {
35                int mirror = l + r - i + 1; // note the +1 shift for even centers
36                k = min(d2[mirror], r - i + 1);
37            }
38            while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
39            d2[i] = k;
40            if (i + k - 1 > r) {
41                l = i - k;
42                r = i + k - 1;
43            }
44        }
45    }
46};
47
48pair<int,int> longest_pal_substring(const string &s, const Manacher &M) {
49    // Returns (start, length) of the LPS
50    int n = (int)s.size();
51    int bestLen = 0, bestL = 0;
52    // Check odd centers
53    for (int i = 0; i < n; ++i) {
54        int len = 2 * M.d1[i] - 1;
55        int L = i - M.d1[i] + 1;
56        if (len > bestLen) {
57            bestLen = len;
58            bestL = L;
59        }
60    }
61    // Check even centers
62    for (int i = 0; i < n; ++i) {
63        int len = 2 * M.d2[i];
64        int L = i - M.d2[i];
65        if (len > bestLen) {
66            bestLen = len;
67            bestL = L;
68        }
69    }
70    return {bestL, bestLen};
71}
72
73int main() {
74    ios::sync_with_stdio(false);
75    cin.tie(nullptr);
76
77    string s;
78    // Example usage: read a string; if no input, use a default example.
79    if (!(cin >> s)) s = "abacdfgdcaba"; // default string
80
81    Manacher M;
82    M.build(s);
83
84    auto [L, len] = longest_pal_substring(s, M);
85
86    cout << "String: " << s << "\n";
87    cout << "Longest Palindromic Substring: '" << s.substr(L, len) << "'\n";
88    cout << "Start index: " << L << ", Length: " << len << "\n\n";
89
90    // Optionally, print sample radii around a few centers
91    cout << "Odd radii (d1):\n";
92    for (int i = 0; i < (int)s.size(); ++i) cout << M.d1[i] << (i + 1 == (int)s.size() ? '\n' : ' ');
93    cout << "Even radii (d2):\n";
94    for (int i = 0; i < (int)s.size(); ++i) cout << M.d2[i] << (i + 1 == (int)s.size() ? '\n' : ' ');
95
96    return 0;
97}
98

This program builds Manacher’s odd (d1) and even (d2) radii in O(n) time. It then scans all centers to extract the longest palindromic substring by comparing derived lengths: 2*d1[i]−1 for odd and 2*d2[i] for even. The mirror and boundary logic ensure minimal redundant comparisons.

Time: O(n)Space: O(n)
Count total palindromic substrings using d1 and d2
1#include <bits/stdc++.h>
2using namespace std;
3
4// Build d1 and d2 as in Manacher's algorithm
5void manacher(const string &s, vector<int> &d1, vector<int> &d2) {
6    int n = (int)s.size();
7    d1.assign(n, 0);
8    int l = 0, r = -1;
9    for (int i = 0; i < n; ++i) {
10        int k = 1;
11        if (i <= r) k = min(d1[l + r - i], r - i + 1);
12        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) ++k;
13        d1[i] = k;
14        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;
15    }
16    d2.assign(n, 0);
17    l = 0; r = -1;
18    for (int i = 0; i < n; ++i) {
19        int k = 0;
20        if (i <= r) k = min(d2[l + r - i + 1], r - i + 1);
21        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
22        d2[i] = k;
23        if (i + k - 1 > r) l = i - k, r = i + k - 1;
24    }
25}
26
27int main() {
28    ios::sync_with_stdio(false);
29    cin.tie(nullptr);
30
31    string s;
32    if (!(cin >> s)) s = "aaaaa"; // default: many palindromes
33
34    vector<int> d1, d2;
35    manacher(s, d1, d2);
36
37    // Total palindromic substrings = sum(d1) + sum(d2)
38    long long total = 0;
39    for (int x : d1) total += x;
40    for (int x : d2) total += x;
41
42    cout << "String: " << s << "\n";
43    cout << "Total palindromic substrings: " << total << "\n";
44
45    // Optionally, show per-prefix cumulative counts using a sweep
46    long long cum = 0;
47    cout << "Cumulative palindromic substrings by center index order (for illustration):\n";
48    for (int i = 0; i < (int)s.size(); ++i) {
49        cum += d1[i];
50        cum += d2[i];
51        cout << cum << (i + 1 == (int)s.size() ? '\n' : ' ');
52    }
53
54    return 0;
55}
56

This program computes d1 and d2 and sums them to count all palindromic substrings in O(n). It uses 64-bit integers to avoid overflow because the number of palindromic substrings can be Θ(n^2) even though computation is linear.

Time: O(n)Space: O(n)
Unified Manacher with transformed string and separators (single p array)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Build transformed string T with sentinels '^' and '$' and separator '#'.
5// Example: s = "aba" -> T = "^#a#b#a#$"
6string transform_with_separators(const string &s) {
7    string t;
8    t.reserve(2 * (int)s.size() + 3);
9    t.push_back('^'); // left sentinel not in input
10    t.push_back('#');
11    for (char c : s) {
12        t.push_back(c);
13        t.push_back('#');
14    }
15    t.push_back('$'); // right sentinel not in input
16    return t;
17}
18
19// Manacher on transformed string. p[i] = radius in T (number of matched chars to one side).
20vector<int> manacher_transformed(const string &T) {
21    int m = (int)T.size();
22    vector<int> p(m, 0);
23    int C = 0, R = 0; // current center and right boundary (exclusive of unmatched)
24    for (int i = 1; i < m - 1; ++i) { // skip sentinels
25        int mirror = 2 * C - i;
26        if (i < R) p[i] = min(R - i, (mirror >= 0 && mirror < m) ? p[mirror] : 0);
27        // Attempt to expand palindrome centered at i
28        while (T[i + 1 + p[i]] == T[i - 1 - p[i]]) ++p[i];
29        // If palindrome centered at i expands past R, adjust center and right boundary
30        if (i + p[i] > R) {
31            C = i;
32            R = i + p[i];
33        }
34    }
35    return p;
36}
37
38pair<int,int> longest_from_transformed(const string &s, const vector<int> &p) {
39    // Find the best center in T and map back to (start, length) in s.
40    // In transformed space, real characters are at odd indices starting from 2.
41    int m = (int)p.size();
42    int bestCenter = 0, bestLen = 0;
43    for (int i = 0; i < m; ++i) {
44        if (p[i] > bestLen) {
45            bestLen = p[i];
46            bestCenter = i;
47        }
48    }
49    // Map back: start = (center - maxLen)/2 in original string; length = maxLen
50    int start = (bestCenter - bestLen) / 2 - 1; // subtract 1 for leading '^'
51    // Because T = '^' '#' s0 '#' s1 '#' ... '#' s_{n-1} '#' '$'
52    // Positions: index 0 '^', 1 '#', then alternating s and '#'
53    // Derivation yields start = (bestCenter - bestLen - 1)/2
54    start = (bestCenter - bestLen - 1) / 2;
55    int length = bestLen;
56    return {max(0, start), max(0, length)};
57}
58
59int main() {
60    ios::sync_with_stdio(false);
61    cin.tie(nullptr);
62
63    string s;
64    if (!(cin >> s)) s = "babad";
65
66    string T = transform_with_separators(s);
67    vector<int> p = manacher_transformed(T);
68
69    auto [L, len] = longest_from_transformed(s, p);
70    cout << "String: " << s << "\n";
71    cout << "Longest Palindromic Substring (via transformed): '" << s.substr(L, len) << "'\n";
72
73    // Optional: show top few centers and their radii in transformed space
74    // Note: p includes separators; palindromes of both parities are unified here.
75    int shown = 0;
76    for (int i = 0; i < (int)p.size() && shown < 8; ++i) {
77        if (p[i] > 0 && T[i] != '^' && T[i] != '$') {
78            cout << "Center i=" << i << " (char '" << T[i] << "') has radius p[i]=" << p[i] << " in T\n";
79            ++shown;
80        }
81    }
82
83    return 0;
84}
85

This version inserts separators to unify odd and even palindromes, runs a single Manacher pass to compute p, and then maps the best center back to the original string to recover the longest palindrome. Separators avoid even/odd branching but require careful index mapping.

Time: O(n)Space: O(n)