SyntaxPilot
Courses/Competitive Programming/Lesson 74
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 74 of 90

Manacher's algorithm

queued

These are the notes for Competitive Programming episode 74. A palindrome reads the same forwards and backwards. Manacher's algorithm finds, for every centre of a string, the radius of the longest palindrome around it, in O(n). It keeps a box [l, r], the palindrome found so far that reaches furthest right; for a centre i inside it, the mirror j = l + r − i already has an answer, so the radius starts at min(d[j], r − i + 1) and only the part past r is checked. Mirror Street (the longest palindromic stretch) shows expand-around-every-centre (TLE) and a real bug: odd centres only gives 1 a instead of 4 abba, fixed by putting # between the letters. Palindrome Count (count palindromic substrings) is one line: the sum of d[i] / 2, in a long long. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A big rangoli is drawn on the floor at Diwali. For every small motif in it you want to know how far the pattern is symmetric around that motif. The slow way measures from scratch every time. But if you already know the big rangoli is symmetric from l to r, then a motif on its right half is the mirror image of a twin on its left half, which you have already measured. So the right motif is at least as symmetric as its twin, but only up to the edge of the big rangoli: beyond that, the mirror tells you nothing. You only measure the new part.

Problem M1 · Mirror Street

(Written for this course.)

  • A street has n houses, each colour a lowercase letter, n ≤ 10^6.
  • Print the length of the longest stretch that reads the same from both ends, and the stretch itself if it has at most 20 letters (else ...).
kayakabba

The longest palindrome is kayak: 5 kayak. (abba has length 4.)

Every palindrome has a centre: a letter for odd length (kayak around y), a gap between two letters for even length (abba between the two bs). A string of length n has 2n − 1 centres.

Attempt 1: expand around every centre (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    int len = 0, start = 0;
    for (int c = 0; c < 2 * n - 1; c++) {          // every centre: a letter or a gap
        int lo = c / 2, hi = lo + c % 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) lo--, hi++;   // walk outwards
        if (hi - lo - 1 > len) len = hi - lo - 1, start = lo + 1;
    }
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}
kayakabba
5 kayak

On a million identical houses, every centre walks almost to the end of the street: about n²/2 comparisons.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    int len = 0, start = 0;
    for (int c = 0; c < 2 * n - 1; c++) {          // every centre: a letter or a gap
        int lo = c / 2, hi = lo + c % 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) lo--, hi++;   // walk outwards
        if (hi - lo - 1 > len) len = hi - lo - 1, start = lo + 1;
    }
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}
Time Limit Exceeded

In the SyntaxPilot compiler this shows Time Limit Exceeded.

The radius and the mirror

  • For odd centres: d[i] = the radius at centre i: s[i − d + 1 .. i + d − 1] is the longest palindrome around i (length 2d − 1).
  • For abacaba: d = 1 2 1 4 1 2 1.
  • Box [l, r]: the palindrome found so far that reaches furthest right.
  • If i ≤ r, its mirror in the box is j = l + r − i. Because the box is a palindrome, the letters around i are the reversed letters around j, so whatever palindrome j has inside the box, i has too.
  • Start with k = min(d[j], r − i + 1) (capped at the edge of the box), then expand while t[i − k] == t[i + k].
s = a b a c a b a        box [0, 6] around the c (i = 3, d = 4)
i = 5 → mirror j = 0 + 6 − 5 = 1, d[1] = 2, cap = 6 − 5 + 1 = 2 → start at k = 2
expand: s[5 − 2] = c, s[5 + 2] = out of range → d[5] = 2

Why it is O(n)

If the mirror's palindrome ends strictly inside the box, the expansion fails at once (the mirror already tells us the next letters differ). Otherwise every successful step reads a letter past r and pushes r right. r never moves left, so the total work is linear: the same argument as the Z-box in episode 73.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

int main() {
    string s;
    cin >> s;
    for (int x : manacher(s)) cout << x << " ";
}
abacaba
1 2 1 4 1 2 1 

The even-length bug

Taking the longest odd palindrome (length 2d − 1):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> d = manacher(s);                   // odd centres only
    int len = 0, start = 0;
    for (int i = 0; i < n; i++)
        if (2 * d[i] - 1 > len) len = 2 * d[i] - 1, start = i - d[i] + 1;
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}
kayakabba
5 kayak

The sample passes, but:

abba
1 a

Wrong: abba has length 4, but its centre is a gap, and the code only looks at letters.

The fix: one # between every two letters

Put # between every two letters and at both ends: abba → #a#b#b#a#. Now every centre of s, letter or gap, is a character of t, and every palindrome of t is odd. In t, d[i] − 1 is exactly the length of the palindrome in s, and it starts at (i − len) / 2.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    string t = with_hashes("abba");
    cout << t << "\n";
    for (int x : manacher(t)) cout << x << " ";
}
#a#b#b#a#
1 2 1 2 5 2 1 2 1 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> d = manacher(with_hashes(s));
    int len = 0, start = 0;
    for (int i = 0; i < 2 * n + 1; i++)
        if (d[i] - 1 > len) len = d[i] - 1, start = (i - len) / 2;   // back to s
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}
abba
4 abba
kayakabba
5 kayak

A single house:

z
1 z

The million houses:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    vector<int> d = manacher(with_hashes(s));
    int len = 0, start = 0;
    for (int i = 0; i < 2 * n + 1; i++)
        if (d[i] - 1 > len) len = d[i] - 1, start = (i - len) / 2;   // back to s
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}
1000000 ...

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int slow(const string& s) {                     // check every substring
    int n = s.size(), best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            string u = s.substr(i, j - i + 1);
            if (u == string(u.rbegin(), u.rend())) best = max(best, j - i + 1);
        }
    return best;
}

int main() {
    mt19937 gen(74);
    for (int t = 1; t <= 500; t++) {
        string s(gen() % 14 + 1, 'a');
        for (char& c : s) c = 'a' + gen() % 2;
        vector<int> d = manacher(with_hashes(s));
        int best = *max_element(d.begin(), d.end()) - 1;
        if (best != slow(s)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem M2 · Palindrome Count

(Written for this course.)

  • Count the substrings of s that are palindromes (copies at different positions count separately), |s| ≤ 10^6.
abba

a, b, b, a, bb, abba: 6. The answer can reach n(n + 1)/2 ≈ 5·10^11, so it needs a long long.

Observation: a palindrome of radius d contains smaller palindromes with the same centre (peel one letter off each end). In the # string, centre i holds exactly d[i] / 2 palindromes of s. The answer is Σ d[i] / 2.

Attempt 1: walk out from every centre and count (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    ll cnt = 0;
    for (int c = 0; c < 2 * n - 1; c++) {          // every centre
        int lo = c / 2, hi = lo + c % 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) lo--, hi++, cnt++;   // one palindrome per step
    }
    cout << cnt << "\n";
}
abba
6
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    ll cnt = 0;
    for (int c = 0; c < 2 * n - 1; c++) {          // every centre
        int lo = c / 2, hi = lo + c % 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) lo--, hi++, cnt++;   // one palindrome per step
    }
    cout << cnt << "\n";
}
Time Limit Exceeded

This costs as much as the answer itself: 5·10^11 steps on a million as.

With Manacher

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> d = manacher(with_hashes(s));
    ll cnt = 0;
    for (int x : d) cnt += x / 2;                  // palindromes around each centre
    cout << cnt << "\n";
}
abba
6
aaa
6
chai
4
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    vector<int> d = manacher(with_hashes(s));
    ll cnt = 0;
    for (int x : d) cnt += x / 2;                  // palindromes around each centre
    cout << cnt << "\n";
}
500000500000

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

ll slow(const string& s) {
    int n = s.size();
    ll cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            string u = s.substr(i, j - i + 1);
            if (u == string(u.rbegin(), u.rend())) cnt++;
        }
    return cnt;
}

int main() {
    mt19937 gen(74);
    for (int t = 1; t <= 500; t++) {
        string s(gen() % 14 + 1, 'a');
        for (char& c : s) c = 'a' + gen() % 3;
        ll cnt = 0;
        for (int x : manacher(with_hashes(s))) cnt += x / 2;
        if (cnt != slow(s)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict
check every substring O(n³) hopeless
M1: expand around every centre O(n²) ≈ 5·10^11 TLE
M1: Manacher on #s# O(n) (2n + 1 centres) accepted (~0.02 s)
M2: count by walking O(answer) ≈ 5·10^11 TLE
M2: Σ d[i] / 2 O(n) accepted

Memory: the # string (2n + 1 chars) and one int array of 2n + 1, about 8 MB for n = 10^6.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
odd centres only abba → 1 a even palindromes have a gap centre the #a#b#b#a# string
k = d[l + r - i] without the cap abacabac → last d = 4 instead of 1 past r the mirror says nothing min(d[j], r - i + 1)
int for the count Wrong Answer on large inputs 5·10^11 overflows int long long
forgetting to map back from #s# wrong substring printed indices are doubled len = d − 1, start = (i − len) / 2
expanding without bounds checks Runtime Error or garbage reads outside the string i - k >= 0 && i + k < n
a separator that is in the alphabet Wrong Answer # must be in no input pick a character outside the input

The uncapped version, run for real on abacabac:

1 2 1 4 1 3 1 4

(The correct radii are 1 2 1 4 1 3 1 1.)

Mini project

Write a "palindrome highlighter": read a sentence of lowercase letters (no spaces) and print it with the longest palindrome in capital letters, plus a list of every maximal palindrome (one per centre) of length at least 3.

Practice

These are the homework problems from the episode.

1. Is every prefix of s a palindrome? The prefix s[0..len) has its centre at index len of the # string; it is a palindrome iff d[len] − 1 ≥ len.

Solution (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;

vector<int> manacher(const string& t) {
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;
    }
    return d;
}

int main() {                                        // is each prefix a palindrome?
    string s;
    cin >> s;
    int n = s.size();
    string t = "#";
    for (char c : s) t += c, t += '#';
    vector<int> d = manacher(t);
    for (int len = 1; len <= n; len++) {
        int centre = len;                           // the centre of s[0..len) in t
        cout << (d[centre] - 1 >= len ? 1 : 0);     // the palindrome there covers the whole prefix
    }
    cout << "\n";
}
abacaba
1010001

2. The longest palindromic prefix of s. Use solution 1 and take the largest len that prints 1. (Or: the prefix function of s + '#' + reverse(s) at the last position, from episode 72.)

3. The shortest string to add in front of s to make it a palindrome. If the longest palindromic prefix has length L, add the reverse of s[L..] in front.

Hint

For aacecaaa: the longest palindromic prefix is aacecaa (7), so add the reverse of a: aaacecaaa.

4. Count only the odd-length palindromes. Those are centred at letters, which are the odd indices of the # string: sum d[i] / 2 over odd i only (equivalently, sum d over odd-only Manacher on s).

Hint

For abba the odd ones are just the four letters: 4. For aaa: a, a, a, aaa = 4.

Quick quiz

// the box is [l, r] = [2, 10], now i = 8
// the mirror j = l + r - i has d[j] = 5
// what is k before the while loop?

A) k = 3 · B) k = 5 · C) k = 1 · D) k = 8

Answer

A. j = 2 + 10 − 8 = 4, and k = min(d[4], r − i + 1) = min(5, 3) = 3. The mirror's palindrome sticks out past the box, so only 3 is guaranteed; the while loop checks the rest.

Interview questions

  1. What does Manacher's algorithm compute? For every centre, the radius of the longest palindrome around it, in O(n).
  2. What is the mirror trick? Inside the rightmost palindrome [l, r], position i mirrors j = l + r − i, so its radius is at least min(d[j], r − i + 1).
  3. Why is it O(n)? Every successful expansion moves r to the right, and r never moves left.
  4. How are even-length palindromes handled? Insert a separator between all letters (and at both ends) so every palindrome becomes odd.
  5. How do you count palindromic substrings? Σ d[i] / 2 over the separator string.
  6. Longest palindromic substring alternatives? Expand around centres O(n²), DP O(n²), hashing + binary search O(n log n), Manacher O(n).
  7. How is it related to the Z-algorithm? Both keep the rightmost-reaching box and reuse an earlier answer capped at the box's edge.

Glossary

Term Meaning Example
Palindrome A string equal to its reverse kayak, abba
Centre The middle letter (odd) or middle gap (even) y in kayak
Radius d[i] How far the palindrome at centre i reaches, counting the centre 4 at c in abacaba
Expand around centre Walk outwards while both ends match the brute force
Box [l, r] The palindrome found so far that reaches furthest right [0, 6] in abacaba
Mirror j = l + r − i The position reflected through the box's centre i = 5 → j = 1
Manacher's algorithm O(n) radii using the box and the mirror min(d[j], r − i + 1)
Separator string #s# # between all letters and at both ends #a#b#b#a#
Palindromic substring A substring that is a palindrome bb in abba
long long 64-bit integer 500000500000
Amortised O(n) Total work bounded over the whole run r only moves right
Stress test Fast vs brute force on many random inputs all 500 tests passed
Z-box The same box idea for prefix matches (episode 73) [l, r)
Trie A tree of prefixes (next episode) names in a phone

Summary

  • d[i] = palindrome radius at centre i; Manacher fills it in O(n): mirror j = l + r − i, start at min(d[j], r − i + 1), expand, move the box.
  • Even palindromes: run it on #a#b#…#; length = d − 1, start = (i − len) / 2.
  • Count palindromic substrings: Σ d[i] / 2 in a long long.

Solutions in C++, Java and Python

Problem M1 · Mirror Street

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> d = manacher(with_hashes(s));
    int len = 0, start = 0;
    for (int i = 0; i < 2 * n + 1; i++)
        if (d[i] - 1 > len) len = d[i] - 1, start = (i - len) / 2;   // back to s
    cout << len << " " << (len <= 20 ? s.substr(start, len) : "...") << "\n";
}

Java (checked on the samples)

import java.io.*;

public class Main {
    static int[] manacher(byte[] t) {                   // d[i]: t[i-d+1 .. i+d-1] is a palindrome
        int n = t.length;
        int[] d = new int[n];
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : Math.min(d[l + r - i], r - i + 1);   // the mirror, capped
            while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
            d[i] = k;
            if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
        }
        return d;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();
        byte[] t = new byte[2 * n + 1];                 // #a#b#b#a#
        for (int i = 0; i < 2 * n + 1; i++) t[i] = (i % 2 == 0) ? (byte) '#' : (byte) s.charAt(i / 2);
        int[] d = manacher(t);
        int len = 0, start = 0;
        for (int i = 0; i < 2 * n + 1; i++)
            if (d[i] - 1 > len) { len = d[i] - 1; start = (i - len) / 2; }
        System.out.println(len + " " + (len <= 20 ? s.substring(start, start + len) : "..."));
    }
}

Python

import sys

def manacher(t):                         # d[i]: t[i-d+1 .. i+d-1] is a palindrome
    n = len(t)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)   # the mirror, capped
        while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
            k += 1                       # expand
        d[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    return d

s = sys.stdin.readline().strip()
d = manacher("#" + "#".join(s) + "#")   # abba -> #a#b#b#a#
length, start = 0, 0
for i, x in enumerate(d):
    if x - 1 > length:
        length, start = x - 1, (i - (x - 1)) // 2
print(length, s[start:start + length] if length <= 20 else "...")

Problem M2 · Palindrome Count

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> manacher(const string& t) {          // d[i]: t[i-d+1 .. i+d-1] is a palindrome
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);   // the mirror, capped
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;   // expand
        d[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;   // a box that reaches further
    }
    return d;
}

string with_hashes(const string& s) {           // abba -> #a#b#b#a#
    string t = "#";
    for (char c : s) t += c, t += '#';
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> d = manacher(with_hashes(s));
    ll cnt = 0;
    for (int x : d) cnt += x / 2;                  // palindromes around each centre
    cout << cnt << "\n";
}

Java (checked on the samples and on 100,000 as, which need the long)

import java.io.*;

public class Main {
    static int[] manacher(byte[] t) {
        int n = t.length;
        int[] d = new int[n];
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : Math.min(d[l + r - i], r - i + 1);
            while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;
            d[i] = k;
            if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
        }
        return d;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();
        byte[] t = new byte[2 * n + 1];
        for (int i = 0; i < 2 * n + 1; i++) t[i] = (i % 2 == 0) ? (byte) '#' : (byte) s.charAt(i / 2);
        long cnt = 0;                                   // up to 5 * 10^11
        for (int x : manacher(t)) cnt += x / 2;         // palindromes around each centre
        System.out.println(cnt);
    }
}

Python

import sys

def manacher(t):
    n = len(t)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
            k += 1
        d[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    return d

s = sys.stdin.readline().strip()
print(sum(x // 2 for x in manacher("#" + "#".join(s) + "#")))