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;
}
