Algorithms
Topics:
Manachar’s Algorithm

# Manachar’s Algorithm

Manacher's Algorithm has one single application. It is used to find the Longest Palindromic Sub-string in any string. This algorithm is required to solve sub-problems of some very hard problems. This article explains the basic brute force method first and then moves on to explain the optimized Manacher's Algorithm.

Brute Force Approach:

Find all possible sub-strings using $2$ nested loops, this solution has $O(N ^ 2)$ where $N$ is the length of the given string. Then for every substring, check if it is a palindrome or not in $O(N)$, so the total time complexity is $O(N ^ 3)$.

This solution could be improved by selecting every letter in the given string as the center $O(N)$, then find the longest palindromic substring around this center $O(N)$, so the total time complexity is $O(N ^ 2)$. For example: given string is "$czbza$", when $b$ is selected as the center, it produces the longest palindromic substring "$zbz$".

However, $O(N ^ 2)$ solution could be improved using some clever observations. Following is the optimized solution.

Manacher's Algorithm

Assume the given String $S$ has a length of $N$, $S$ = "$abababa$". Create a string $Q$ of length $2 \cdot N + 1$, by inserting any letter that doesn't appear in the input string (call it special character for the purpose of this article), in the spaces between any $2$ characters. Also, insert this special character in the beginning and the end of the string. If "#" is chosen as special character then the new string $Q$ would look like "$#a#b#a#b#a#b#a#$".

Calculate the longest palindromic substring in each center. Expand around each character $i$ in the new string, then store the number of letters, in the longest palindromic substring with character $i$ as the center, divided by $2$. The stored number is divided by $2$ because the palindromic substring has it's $2$ same parts around the center.

Above process would yield an array $P = [0, 1, 0, 3, 0, 5, 0, 7, 0, 5, 0, 3, 0, 1, 0]$. Each number $m$, in the array $P$, indicates that there are $m$ corresponding letters in both sides around a center $i$. So the palindromic substring = $m$ letters in the left side + center + $m$ letters in right side.

Observation (1):

For the center index $c = 7$ i.e $P[c] = 7$ which has the longest palindromic substring. Notice that the numbers in array $P$ after center $c = 7$ are same as numbers before center $c$, so avoid expanding around all letters after center $c$, however just put their values directly using the Mirror (by copying the first half of array $P$ in its other half) property.

Observation (2):

Unfortunately, Mirror property can't be applied in all cases. For example: $S$ = "$acncacn$", the new string
$Q$ = "$#a#c#n#c#a#c#n#$".
The result array $P$ = $[0,1,0,1,0,5,0,1,0,5,0,1,0,1,0]$.

Consider the center $c = 5$. The mirror property applies in $P[4] = p[6], p[3] = p[7], p[2] = p[8]$. But why $p[1]\; !=\; p[9]$ ? So Mirror property doesn't work in all cases, because in this case there is another palindrome with center $c = 9$. This new palindrome, with center $c = 9$, goes beyond the limits of the first palindrome with center $c = 5$.

Algorithm Steps:

Let the $2$ limits of the first palindrome with center $c$: a left limit $l$, a right limit $r$. $l,r$ have references over the last $2$ corresponding letters in the palindrome sub-string. A letter $w$ with index $i$ in a palindrome substring has a corresponding letter $w'$ with index $i'$ such that the $c - i$ = $i' - c$.

(1) If($p[i] \le r - i'$),

So $p[i'] = p[i]$ which means that palindrome with center $i'$ can't go beyond the original palindrome, so apply the Mirror Property directly.

(2) Else $p[i'] \ge p[i]$,

This means that palindrome with center $i'$ goes beyond the original palindrome, so expanding around this center $i'$ is needed.

Let $d = \;distance\; r - i'$, so expanding around center $i'$ will start from $(i' - d) - 1$ with $(i' + d) + 1 = (r + 1)$ and so on... because the interval $[i' - d: i' + d]$ is already contained in the palindrome with center $i'$.

The algorithm has $2$ nested loops, outer loop check if there will be an expanding around current letter or not. This loop takes $N$ steps.
Inner loop will be used in case of expanding around a letter, but it is guaranteed that it takes at most $N$ steps by using the above $2$ observations.
So the total time = $2 \cdot N = O(N)$.

(3) Update $c, r$ when a palindrome with center $i'$ goes beyond the original palindrome with center $c$.
$c = i', r = i' + p[i']$ as the next expanding will be around center $i'$.

Note: Insert another $2$ different special characters in the front and the end of string $Q$ to avoid bound checking.

Implementation:

#include <bits/stdc++.h>
using namespace std;
#define SIZE 100000 + 1

int P[SIZE * 2];

// Transform S into new string with special characters inserted.
string convertToNewString(const string &s) {
string newString = "@";

for (int i = 0; i < s.size(); i++) {
newString += "#" + s.substr(i, 1);
}

newString += "#\$";
return newString;
}

string longestPalindromeSubstring(const string &s) {
string Q = convertToNewString(s);
int c = 0, r = 0;                // current center, right limit

for (int i = 1; i < Q.size() - 1; i++) {
// find the corresponding letter in the palidrome subString
int iMirror = c - (i - c);

if(r > i) {
P[i] = min(r - i, P[iMirror]);
}

// expanding around center i
while (Q[i + 1 + P[i]] == Q[i - 1 - P[i]]){
P[i]++;
}

// Update c,r in case if the palindrome centered at i expands past r,
if (i + P[i] > r) {
c = i;              // next center = i
r = i + P[i];
}
}

// Find the longest palindrome length in p.

int maxPalindrome = 0;
int centerIndex = 0;

for (int i = 1; i < Q.size() - 1; i++) {

if (P[i] > maxPalindrome) {
maxPalindrome = P[i];
centerIndex = i;
}
}

cout << maxPalindrome << "\n";
return s.substr( (centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
}

int main() {
string s = "kiomaramol\n";
cout << longestPalindromeSubstring(s);
return 0;
}