Manacher's Algorithm - Linear Time Longest Palindromic Substring - Part 4 - GeeksforGeeks

Manacher's Algorithm - Linear Time Longest Palindromic Substring - Part 4 - GeeksforGeeks

Manacher's Algorithm – Linear Time Longest Palindromic Substring – Part 4

In Manacher's Algorithm Part 1 and Part 2, we gone through some of the basics, understood LPS length array and how to calculate it efficiently based on four cases. In Part 3, we implemented the same.
Here we will review the four cases again and try to see it differently and implement the same.
All four cases depends on LPS length value at currentLeftPosition (L[iMirror]) and value of (centerRightPosition – currentRightPosition), i.e. (R – i). These two information are know before which helps us to reuse previous available information and avoid unnecessary character comparison.

Read full article from Manacher's Algorithm - Linear Time Longest Palindromic Substring - Part 4 - GeeksforGeeks