Manacher's algorithm in Python
Computes the radius of the longest palindrome centred at every position in linear time.
- File
manacher.py, 61 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/manacher/. The authors are listed in prov/25Z40B.jsonl.
"""Manacher's algorithm: the maximal palindrome at each of the 2n + 1 centers.
Indices are 0-based. The string s is read through the implicit string
T = # s[0] # s[1] # ... # s[n-1] #, of length m = 2n + 1, where # is a
separator that is not a symbol. T[x] is s[(x - 1) // 2] for odd x and the
separator for even x. Symbols are only tested for equality.
"""
from collections.abc import Hashable, Sequence
def _t_equal(s: Sequence[Hashable], x: int, y: int) -> bool:
"""Test T[x] = T[y] for two positions x and y of the same parity."""
if x % 2 == 0:
return True # two separators
return s[(x - 1) // 2] == s[(y - 1) // 2]
def manacher(s: Sequence[Hashable]) -> list[int]:
"""Return P with P[c] the radius of the maximal palindrome of T at c.
P[c] is also the length, in s, of the longest palindrome with center c:
odd c is the symbol s[(c - 1) // 2], even c is the gap before s[c // 2].
That palindrome is s[(c - P[c]) // 2 .. (c + P[c]) // 2 - 1].
"""
n = len(s)
m = 2 * n + 1 # @line L1
p = [0] * m # @line L2
c, r = 0, 0 # @line L3
for i in range(m): # @line L4
if i < r: # @line L5
p[i] = min(p[2 * c - i], r - i)
while (
i - p[i] - 1 >= 0
and i + p[i] + 1 < m
and _t_equal(s, i - p[i] - 1, i + p[i] + 1)
): # @line L6
p[i] += 1 # @line L7
if i + p[i] > r: # @line L8
c, r = i, i + p[i]
return p # @line L9
def is_palindrome_query(p: list[int], i: int, j: int) -> bool:
"""Return True if s[i..j] (both ends included) is a palindrome, given P."""
if j < i:
return True
return p[i + j + 1] >= j - i + 1
def longest_palindrome(s: Sequence[Hashable]) -> tuple[int, int]:
"""Return (start, length) of the leftmost longest palindromic substring."""
p = manacher(s)
best_c = 0
for c in range(len(p)):
if p[c] > p[best_c]:
best_c = c
return (best_c - p[best_c]) // 2, p[best_c]
test_manacher.py 70 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/manacher/. The authors are listed in prov/25Z40B.jsonl.
import random
from manacher import is_palindrome_query, longest_palindrome, manacher
def brute_radii(s: str) -> list[int]:
"""For each center c, the length of the longest palindrome s[i..j] with i + j + 1 = c."""
n = len(s)
out = [0] * (2 * n + 1)
for i in range(n):
for j in range(i, n):
t = s[i : j + 1]
if t == t[::-1]:
c = i + j + 1
out[c] = max(out[c], j - i + 1)
return out
def brute_longest(s: str) -> tuple[int, int]:
best = (0, 0)
for i in range(len(s)):
for j in range(i, len(s)):
t = s[i : j + 1]
if t == t[::-1] and j - i + 1 > best[1]:
best = (i, j - i + 1)
return best
def test_example() -> None:
assert manacher("abaabaab") == [0, 1, 0, 3, 0, 1, 6, 1, 0, 7, 0, 1, 4, 1, 0, 1, 0]
assert manacher("abacaba") == [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 3, 0, 1, 0]
assert longest_palindrome("banana") == (1, 5)
def test_edges() -> None:
assert manacher("") == [0]
assert longest_palindrome("") == (0, 0)
assert manacher("a") == [0, 1, 0]
for n in range(1, 30):
p = manacher("a" * n)
assert p == [min(c, 2 * n - c) for c in range(2 * n + 1)]
assert longest_palindrome("a" * n) == (0, n)
s = "abc" * 10
assert max(manacher(s)) == 1
assert longest_palindrome(s) == (0, 1)
assert manacher([1, 2, 1]) == [0, 1, 0, 3, 0, 1, 0]
def test_random_against_brute_force() -> None:
rng = random.Random(20251105)
for trial in range(1500):
k = (1, 2, 3)[trial % 3]
n = rng.randrange(0, 16)
s = "".join(rng.choice("abc"[:k]) for _ in range(n))
p = manacher(s)
assert p == brute_radii(s), s
assert longest_palindrome(s) == brute_longest(s), s
for i in range(n):
for j in range(i, n):
t = s[i : j + 1]
assert is_palindrome_query(p, i, j) == (t == t[::-1])
def test_long_input_is_linear() -> None:
s = "ab" * 50000 + "a"
p = manacher(s)
assert p[len(s)] == len(s)
What the next level needs
- the tests did not run in this build