Manacher Algorithm

An optimal \(O(n)\) algorithm for Longest Palindromic Substring problem.

• At the core it is same as expanding from the center, but skips checks in the expansion using symmetry property of palindromes.

We start from left

1. We keep track of longest palindrome at center i in a array p[i].

2. Consider each center (i) and start expanding, say we reach upto \(R = i + \Delta\) index. So, str[L:R] is palindrome.

   Keep track of the longest palindrom radius for the center \(i\) in \(p[i] = \Delta\).

3. Then for any other center \(j = i + \delta\) inside i to R, the surrounding of j is same as of mirror[j] = \(j - \delta\) at max upto the boundary at R.

   This means if p[mirror[j]] is smaller than distance from boundary we can skip this \(j\), else start checking from \(R\).

   In both case, once a region is expanded, the characeters inside it aren't double checked.

4. At last the longest palindrome is found from largest element in p[i].