strings.manacher

Functions

palindromic_string(→ str)

Module Contents

strings.manacher.palindromic_string(input_string: str) → str

>>> palindromic_string('abbbaba')
'abbba'
>>> palindromic_string('ababa')
'ababa'

Manacher’s algorithm which finds Longest palindromic Substring in linear time.

1. first this convert input_string(“xyx”) into new_string(“x|y|x”) where odd

   positions are actual input characters.

2. for each character in new_string it find corresponding length and

   store the length and left,right to store previously calculated info. (please look the explanation for details)

3. return corresponding output_string by removing all “|”