Manachar’s Algorithm - Longest palindromic substring in linear time

August 28, 2022 · 1 min · string-algo · longest · palindrome · substring · named-algo-ds/algo · difficulty/hard | 🖍️

Table of Contents

Problem

Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string

We have already seen simple O(n^2) solution here - Longest Palindromic Substring Problem, but now lets look at Manacher’s Algorithm, which help us find the solution in linear time.

Manacher’s Algorithm

#TODO complete this

Problem#

Manacher’s Algorithm#

Problem

Manacher’s Algorithm