Manacher's Algorithm
Finds the longest palindromic substring in linear time by inserting separators to unify odd/even-length cases, then expanding around each center while reusing the mirror symmetry inside the widest palindrome found so far.
- Category
- Strings
- Time complexity
- O(n)
- Space complexity
- O(n)
Pseudocode
insert separators: unify odd/even palindromes track center c and right edge r of the widest found reuse P[mirror] when inside [c, r) expand past that with direct comparison
Reference implementation
# t = "#" between every char
for i in range(1, len(t)-1):
if i < r: P[i] = min(r-i, P[2*c-i])
while t[i+P[i]+1] == t[i-P[i]-1]: P[i] += 1
if i+P[i] > r: c, r = i, i+P[i]