strings.manacher
================

.. py:module:: strings.manacher


Functions
---------

.. autoapisummary::

   strings.manacher.palindromic_string


Module Contents
---------------

.. py:function:: 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 "|"