Manacher and palindromes

Why this matters when you build with AI

Ask an AI tool for "the longest palindromic substring" and you will often get a function that tries every center and expands outwards. It is correct, and on a string of 200000 letters it takes about 2 * 10^10 steps in the worst case, which is too slow. Ask for a faster version and the tool may return a version that looks like Manacher's algorithm but gets the even centers wrong. The output then looks plausible on short words such as "racecar" and wrong on "abba".

You can catch both problems in a few minutes. Write a brute force that tries every substring. Compare the two on all short strings over a two-letter alphabet, which is a small and complete test set. This lesson builds that habit together with the algorithm.

A prompt that states the limits and the cases you care about:

Write a C++17 function that returns, for every position i of a string s of length n <= 200000,
the largest k such that s[i-k+1 .. i+k-1] is a palindrome (odd length), and the largest k such
that s[i-k .. i+k-1] is a palindrome (even length). Use O(n) time. Explain how you handle even
palindromes separately from odd ones, and give the answer for "abba" by hand before you run code.

A good answer gives two arrays, one for odd and one for even palindromes, runs in O(n), and matches the hand answer for "abba", which is [1, 1, 1, 1] for odd and [0, 0, 2, 0] for even. Check each of those by reading the code, then run it against the brute force on all short strings (section "Check against a brute force" below).

Terms used

A palindrome reads the same forwards and backwards. abba and racecar are palindromes. a is one too.
A substring is a run of consecutive characters of the string. The substring bcb is a substring of abcbd.
A center is the place around which a palindrome grows. An odd palindrome has a center character, such as the c in abcba. An even palindrome has no center character, such as the gap between the two bs in abba.
The radius of a center is the number of characters on one side that match the mirror image. For an odd center i, we store d1[i] = k when s[i-k+1 .. i+k-1] is the longest palindrome centered at i. So the length is 2k - 1.
For an even center between positions i-1 and i, we store d2[i] = k when s[i-k .. i+k-1] is the longest palindrome there. So the length is 2k.
O(...) means the work grows no faster than the given expression as n grows.
A hash is a number computed from a string, so that equal strings get equal numbers. Two different strings can get the same number, which is called a collision. The lesson on rolling hashes covers hashing in depth. Here we only use it as a fast equality test.

The idea: a palindrome is a mirror image

Take the string abacaba. Its center is the c at position 3. Every character on the left matches the character at the same distance on the right: a with a, b with b, a with a. So the whole string is a palindrome and d1[3] = 4.

Now take the position 4, the a just right of the center. Its mirror image across the center 3 is position 2. The palindrome around 4 is limited by what happens around its mirror. This is the whole idea of Manacher's algorithm: once you know a large palindrome, the palindromes inside it are mirror images of palindromes you already computed.

The naive method is to expand from every center, one step at a time, until the characters stop matching. That is correct. But on the string aaaa...a of length n, every center expands to the nearest end, and the total work is about n^2 / 2 comparisons. Manacher's algorithm avoids that work by reusing what it has already learnt about the mirror.

Manacher's algorithm for odd centers

The rule

Keep a window [l, r], the palindrome with the furthest right end found so far. Start with l = 0 and r = -1, an empty window.

For a new center i:

If i is outside the window (i > r), start the radius at 1 and expand.
If i is inside the window, its mirror is l + r - i. The radius at i is at least min(d1[mirror], r - i + 1), because the palindrome around the mirror lies inside the window. Start there and expand.

After expanding, if the palindrome at i ends beyond r, move the window to it.

Why this is linear

Each step of the expansion loop moves the right end i + k - 1 further to the right, and it never moves back. The window's right end only increases. So the total number of successful character comparisons is at most n, plus one failed comparison for each center. The whole loop is O(n).

A trace on abacaba

The array d1 for abacaba is worked out below. The values come from the Python trace in section "Trace in Python", so the trace matches the output.

index:   0  1  2  3  4  5  6
char:    a  b  a  c  a  b  a
d1:      1  2  1  4  1  2  1

At index 3 the window becomes [0, 6] with d1[3] = 4. At index 4 the mirror is 0 + 6 - 4 = 2, and d1[2] = 1, so the start radius is min(1, 6 - 4 + 1) = 1. The check of the next pair, positions 3 and 5, is c against b, so the radius stays 1. At index 5 the mirror is 1 with d1[1] = 2, and the start radius is min(2, 2) = 2. Positions 3 and 7 are outside the string, so the radius stays 2 and the window does not move.

Manacher's algorithm for even centers

An even center sits between two positions, so there is no center character to start from. Store the radius at the gap between positions i-1 and i. For abba, the gap between the two bs is at i = 2, and the palindrome is s[1 .. 2], which is bb, so d2[2] = 2.

The code is the same idea with two changes: the start radius is 0 when i is outside the window, and the window is written as [i-k, i+k-1]. The mirror is l + r - i + 1, because the gap sits between two positions and not on one of them. Check it on abba by hand: d2 should be [0, 0, 2, 0]. The Python trace in section "Trace in Python" prints exactly that.

Counting palindromic substrings

Every palindromic substring has exactly one center, either odd or even. A palindrome centered at i with radius k contains k palindromes of odd length centered there: lengths 1, 3, ..., 2k - 1. So the odd centers give d1[i] palindromes each. The even centers give d2[i] each, one for each even length up to 2k.

So the count is sum(d1) + sum(d2). For aaaa the arrays are d1 = [1, 2, 2, 1] and d2 = [0, 1, 2, 1], and the count is 6 + 4 = 10. The Python trace in section "Trace in Python" checks this against a brute count and gets 10.

Trace in Python

This program is short and needs no input. It computes both arrays for four strings, prints the palindrome count from the arrays and from a brute count, and shows that the two agree. Run it with python3 -I manacher_trace.py. The output below was produced on the machine used for this lesson.

Python · editable

abcdba d1 = [1, 1, 1, 1, 1, 1] d2 = [0, 0, 0, 0, 0, 0] count = 6 brute = 6
aaaa d1 = [1, 2, 2, 1] d2 = [0, 1, 2, 1] count = 10 brute = 10
abba d1 = [1, 1, 1, 1] d2 = [0, 0, 2, 0] count = 6 brute = 6
racecar d1 = [1, 1, 1, 4, 1, 1, 1] d2 = [0, 0, 0, 0, 0, 0, 0] count = 10 brute = 10

Mirror argument, in plain words

The reuse step works because of one rule: a palindrome that lies inside the window is a mirror image of the palindrome at its mirror. The mirror of a palindrome is also a palindrome, so its radius carries over. The only case where we must expand past the copied value is when the copied palindrome reaches the window edge. Then we do not know what lies beyond the edge, so we check each new pair. Every check that succeeds moves the right end forward, and that is what keeps the total work linear.

The C++ code

The header below has the Manacher loops, the palindrome counting, and the one-change solution from the next section. It uses the standard C++17 headers. Compile with g++ -std=c++17 -O2.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
 
static const u64 MODH = (1ULL << 61) - 1;
 
// (a * b) mod (2^61 - 1), using 128-bit intermediate product
static u64 mulmod(u64 a, u64 b) {
    __uint128_t c = (__uint128_t)a * b;
    u64 r = (u64)((c >> 61) + (c & MODH));
    r = (r & MODH) + (r >> 61);
    if (r >= MODH) r -= MODH;
    return r;
}
 
struct Hash {
    vector<u64> h, p;
    u64 B;
    Hash(const string& s, u64 base) : h(s.size() + 1, 0), p(s.size() + 1, 1), B(base) {
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = (mulmod(h[i], B) + (u64)(unsigned char)s[i]) % MODH;
            p[i + 1] = mulmod(p[i], B);
        }
    }
    // hash of s[l .. l+len)
    u64 get(int l, int len) const {
        u64 v = h[l + len] + MODH - mulmod(h[l], p[len]);
        return v % MODH;
    }
};
 
// Longest substring that becomes a palindrome after changing at most one character.
// Equivalent: at most one mismatched pair (s[i], s[j]) inside the substring.
int longest_one_change(const string& s, u64 base) {
    int n = s.size();
    if (n == 0) return 0;
    string rs(s.rbegin(), s.rend());
    Hash hs(s, base), hr(rs, base);
 
    // Manacher: d1[i] = odd radius (palindrome [i-k+1, i+k-1]),
    //           d2[i] = even radius (palindrome [i-k, i+k-1]).
    vector<int> d1(n), d2(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
        d2[i] = k;
        if (i + k - 1 > r) { l = i - k; r = i + k - 1; }
    }
 
    // After the first mismatch at (L, R), count how many more pairs match:
    // largest t with s[L-1-j] == s[R+1+j] for all j < t. Binary search with hashes.
    auto ext = [&](int L, int R) {
        int lo = 0, hi = min(L, n - 1 - R);
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            // s[L-1], s[L-2], ... is rs starting at index n-L
            if (hr.get(n - L, mid) == hs.get(R + 1, mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    };
 
    int best = 1;
    for (int i = 0; i < n; i++) {
        best = max(best, 2 * d1[i] - 1);
        int L = i - d1[i], R = i + d1[i];
        if (L >= 0 && R < n) best = max(best, (R - L + 1) + 2 * ext(L, R));
    }
    for (int i = 0; i < n; i++) {
        best = max(best, 2 * d2[i]);
        int L = i - d2[i] - 1, R = i + d2[i];
        if (L >= 0 && R < n) best = max(best, (R - L + 1) + 2 * ext(L, R));
    }
    return best;
}
 
// Brute force: try every substring and count mismatched pairs. O(n^3).
int brute_one_change(const string& s) {
    int n = s.size(), best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int mism = 0;
            for (int a = i, b = j; a < b; a++, b--)
                if (s[a] != s[b]) mism++;
            if (mism <= 1) best = max(best, j - i + 1);
        }
    return best;
}

The main function reads n and then the string, and prints the answer. It picks a random base in the range [500, MODH - 500) with a seed from the clock, so no fixed test can be built against it.

#include "one_change.hpp"
 
int main() {
    int n;
    string s;
    cin >> n >> s;
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    u64 base = rng() % (MODH - 1000) + 500;
    cout << longest_one_change(s, base) << "\n";
    return 0;
}

Running the sample input from the problem gives:

$ printf '6 abcdba\n' | ./one_change
6
$ printf '5 abbca\n' | ./one_change
5

The one-change problem

Statement

You are given a string s of n lowercase letters, with 1 <= n <= 200000. You may change at most one character of s to another lowercase letter. The change must lie inside the substring you pick. Find the largest length of a substring that is a palindrome after this change.

Input: the first line holds n. The second line holds s. Output: one integer.

Examples: for abcdba the whole string works, by changing the d to a c, which gives abccba, so the answer is 6. For abbca the answer is 5, by changing the c to a b, which gives abbba.

The idea

A substring can be fixed by one change exactly when it has at most one mismatched pair. A pair is two positions at the same distance from the ends, such as the first and last characters. If the substring has zero mismatched pairs it is already a palindrome. If it has one, change either character of that pair.

So for each center we want the longest substring that has at most one mismatched pair. Here is how the search works:

Run Manacher's algorithm. For each center, it gives the radius k where the first mismatch sits: positions L = i - k and R = i + k for an odd center. Everything inside is a palindrome.
Accept the mismatch at (L, R). We can then extend outwards past it, but only while the pairs beyond it match. That extension is the number t of matching pairs at (L-1, R+1), (L-2, R+2), and so on.
The substring from L - t to R + t has one mismatch and t matching pairs on each side beyond it, so its length is (R - L + 1) + 2t.

The number t can be found by a binary search, because the condition "the first t pairs match" gets false once t is too large and never becomes true again. Each test of a candidate t compares two substrings of the same length, one reversed. Equal substrings have equal hashes, so one hash comparison replaces a loop. The binary search takes O(log n) tests per center.

A worked example: abcdba

Take the even center between positions 2 and 3, which holds c and d. Manacher gives d2[3] = 0, so the first mismatch is L = 2 (c) and R = 3 (d). Now count matching pairs outwards.

pair 1: position 1 (b) and position 4 (b)   match
pair 2: position 0 (a) and position 5 (a)   match
no more positions on the left, so t = 2
length = (3 - 2 + 1) + 2 * 2 = 2 + 4 = 6

The substring is abcdba, and the change is d to c, which gives abccba. The program prints 6, the same as the brute force.

Complexity

Manacher's part is O(n). The extension is a binary search of O(log n) hash tests for each of the at most 2n centers. So the total is O(n log n) time and O(n) memory. For n = 200000 the program ran in about 0.14 s on the machine used for this lesson, with a random two-letter string. Your time will differ on another machine.

Why not extend directly

A direct loop from L - 1 and R + 1 is simpler, and it is correct. But one center can compare up to n / 2 pairs, and there are up to 2n centers, so the worst case is on the order of n^2 comparisons. For n = 200000 that is far too slow. The hash turns each extension into a binary search.

Hashing as a cross-check

The hash in this lesson is only as good as its equality test. Two different substrings can, rarely, get the same hash. That is a collision. With the modulus 2^61 - 1 and a random base, the chance of a collision for one comparison of two different strings of length at most n is, by the usual polynomial argument, at most about n / 2^61. For n = 200000 that is about 10^-13 per comparison. There are about n log n comparisons in one run, so the total chance of one wrong answer is still very small. This is an estimate from the formula, not a measured rate.

The check the lesson relies on is a direct test. The program hash_crosscheck compares the hash equality of two random substrings with the plain string comparison, 200000 times:

$ ./hash_crosscheck
hash agrees with direct comparison on 200000 checks (126036 equal)

If the two ever disagreed, the program would print the string and stop. Keep this kind of check in your own testing when you use a hash inside a contest solution. A hash that is wrong only on rare inputs is the hardest bug to find by reading code.

Check against a brute force

Random tests alone can miss small edge cases such as the first or last position. The stress test below tries every string over the letters a, b, c of length 1 to 8, which is 3 + 9 + ... + 6561 strings, and then 20000 random strings of length up to 60. For each one it compares the fast answer with the brute force answer.

$ ./one_change_stress
all 29840 cases agree with brute force

The large random inputs also ran in the time given above. The brute force is O(n^3) and is only used on the small strings.

What was checked here: the one-change solution, the Manacher arrays on the sample strings (their palindrome counts match a brute count), and the hash against direct comparison. Nothing else in this lesson has been checked beyond those runs.

Common mistakes

Using the odd formula for even centers. The symptom is an answer that is off by one on strings such as abba, where the even palindrome bb is missed. Check d2 by hand on abba: it should be [0, 0, 2, 0].
Off-by-one on the window update. Writing if (i + k > r) instead of if (i + k - 1 > r) changes the window by one, and the mirror values can then be wrong. Print d1 and d2 for abacaba and abba and compare them with the arrays above.
Forgetting that the odd length is 2k - 1 and the even length is 2k. Using 2k for both gives answers that are too long for odd palindromes.
Using the value d1[i] for the mismatch position without checking the bounds. When L < 0 or R >= n, there is no mismatch, and the palindrome already touches an end. The code checks both bounds before the extension.
Comparing hashes with different bases or different lengths. The two hashes in the extension must use the same base and the same modulus, and the same substring length. Otherwise the answer changes from run to run.
Reading the problem wrongly as "change any character anywhere". The change must be inside the chosen substring, so a change outside it does not make the substring a palindrome.

Checklist

Write the brute force first, then the fast version, and compare them on all strings over a two-letter alphabet up to length 8.
Check odd and even centers separately. Test abba (even) and aba (odd) by hand.
Write the window update as if (i + k - 1 > r) for odd centers and the same condition for even centers, then check the mirror index l + r - i for the odd case and l + r - i + 1 for the even case.
Check the bounds L >= 0 and R < n before a mismatch is used.
Compare every hash equality with a direct comparison in at least one test run.
Use long long or int for lengths only after checking that the value fits. Here n is at most 200000, so int is enough.
Time the largest input, and check that the time is near the expected O(n log n).

Summary

Manacher's algorithm gives the odd and even palindrome radius of every center in linear time, by copying values from the mirror of each center inside the best palindrome found so far. Counting palindromic substrings is then the sum of the radii. For the one-change problem, each center has one first mismatch, and the answer for that center comes from a hash-based binary search for how far the matching pairs extend past it. The fast answer agrees with a brute force on all short strings we tried.

Practice

Problem 1: radii by hand

Compute d1 and d2 for the string abba by hand, using the rules above, before you run any code. Then count the palindromic substrings.

Show the answer

Hint: odd centers start at radius 1 at every position. The even center between the two bs has radius 2 before the outer pairs fail.

Answer: d1 = [1, 1, 1, 1] and d2 = [0, 0, 2, 0]. The sum is 4 + 2 = 6. The six palindromes are a, b, b, a, bb and abba. The program prints 6 for this string.

Problem 2: count the palindromes in aaaa

Count the palindromic substrings of aaaa using the formula sum(d1) + sum(d2), then check your count against a brute force.

Show the answer

Hint: every substring of aaaa is a palindrome, so the answer is the number of substrings. A string of length 4 has 4 + 3 + 2 + 1 substrings.

Answer: 10. The arrays are d1 = [1, 2, 2, 1] and d2 = [0, 1, 2, 1]. The sums are 6 and 4. The brute count is also 10.

Problem 3: one change on a short string

Find the longest substring of abcde that becomes a palindrome after changing at most one character inside it. Give the substring and the change.

Show the answer

Hint: list the substrings of length 3 first. A length-4 substring has two mismatched pairs in abcde, so it cannot work.

Answer: length 3. For example abc becomes aba after changing the c to an a. The program prints 3.

Problem 4: explain the extension step

The one-change solution uses a binary search with hashes to find how far the matching pairs extend past the first mismatch. Explain, in your own words, why the search is valid: why does "the first t pairs match" get false once t is too large, and never becomes true again for a larger t?

Show the answer

Hint: think about what the pairs are: each one is a position on the left and its mirror on the right.

Answer: if the first t pairs match, then every smaller number of pairs also matches, because the matching pairs form a prefix of the sequence of pairs. So the condition is true up to some largest t and false after it. A binary search on a true-then-false condition finds that largest t in O(log n) tests.

Problem 5: find the first mismatch

Write a function that, given the string and an odd center i, returns the first mismatched pair (L, R) using d1, or reports that none exists. Then check it on abcdba.

Show the answer

Hint: the first mismatch is L = i - d1[i] and R = i + d1[i], and it only exists when both are inside the string.

Answer: for the odd center i = 2 (the c), d1[2] = 1, so L = 1 and R = 3. Those are b and d, a mismatch. The function returns (1, 3). For the center i = 0 the left index is negative, so the function reports no mismatch.