StringsString Algorithms

Manacher's Algorithm

Compute the palindrome radius around every center in O(n) by reusing mirrored radii inside the rightmost known palindrome.

Learn Manacher's Algorithm →
a
#
0
b
1
#
2
a
3
#
4
b
5
#
6
a
7
#
8
d
9
#
10
P
0
1
2
3
4
5
6
7
8
9
10
1/24Insert '#' between characters so every palindrome has odd length (5 chars become 11). P[i] will hold the radius of the palindrome centred at i.
Current center iCharacters being expandedRightmost palindrome [c - r, c + r]Longest palindrome
PseudocodeLearn Manacher's Algorithm →
1t = "#" + "#".join(s) + "#"; P = [0]*len(t); c = r = 0
2for i in 0 .. len(t)-1:
3  mirror = 2*c - i
4  if i < r: P[i] = min(r - i, P[mirror])
5  while t[i + P[i] + 1] == t[i - P[i] - 1]: P[i] += 1
6  if i + P[i] > r: c = i; r = i + P[i]
7answer = longest P[i]; palindrome = s[(i - P[i]) / 2 .. +P[i]]
Variables
c0
r0
Complexity
best O(n)
avg O(n)
worst O(n)
space O(n)
Speed