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
- What does Manacher's algorithm compute? For every centre, the radius of the longest palindrome around it, in O(n).
- 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).
- Why is it O(n)? Every successful expansion moves r to the right, and r never moves left.
- How are even-length palindromes handled? Insert a separator between all letters (and at both ends) so every palindrome becomes odd.
- How do you count palindromic substrings? Σ d[i] / 2 over the separator string.
- Longest palindromic substring alternatives? Expand around centres O(n²), DP O(n²), hashing + binary search O(n log n), Manacher O(n).
- 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 atmin(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) + "#")))