 ### C++ Manachars 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\left({N}^{2}\right)$ where $N$ is the length of the given string. Then for every substring, check if it is a palindrome or not in $O\left(N\right)$, so the total time complexity is $O\left({N}^{3}\right)$.

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

However, $O\left({N}^{2}\right)$ 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%u22C5N+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=\left[0,1,0,3,0,5,0,7,0,5,0,3,0,1,0\right]$. 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\left[c\right]=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$ = $\left[0,1,0,1,0,5,0,1,0,5,0,1,0,1,0\right]$.

Consider the center $c=5$. The mirror property applies in $P\left[4\right]=p\left[6\right],p\left[3\right]=p\left[7\right],p\left[2\right]=p\left[8\right]$. But why $p\left[1\right]\phantom{\rule{thickmathspace}{0ex}}!=\phantom{\rule{thickmathspace}{0ex}}p\left[9\right]$ ? 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}^{%u2032}$ with index ${i}^{%u2032}$ such that the $c%u2212i$ = ${i}^{%u2032}%u2212c$.

(1) If($p\left[i\right]%u2264r%u2212{i}^{%u2032}$),

So $p\left[{i}^{%u2032}\right]=p\left[i\right]$ which means that palindrome with center ${i}^{%u2032}$ can't go beyond the original palindrome, so apply the Mirror Property directly.

(2) Else $p\left[{i}^{%u2032}\right]%u2265p\left[i\right]$,

This means that palindrome with center ${i}^{%u2032}$ goes beyond the original palindrome, so expanding around this center ${i}^{%u2032}$ is needed.

Let $d=\phantom{\rule{thickmathspace}{0ex}}distance\phantom{\rule{thickmathspace}{0ex}}r%u2212{i}^{%u2032}$, so expanding around center ${i}^{%u2032}$ will start from $\left({i}^{%u2032}%u2212d\right)%u22121$ with $\left({i}^{%u2032}+d\right)+1=\left(r+1\right)$ and so on... because the interval $\left[{i}^{%u2032}%u2212d:{i}^{%u2032}+d\right]$ is already contained in the palindrome with center ${i}^{%u2032}$.

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%u22C5N=O\left(N\right)$.

(3) Update $c,r$ when a palindrome with center ${i}^{%u2032}$ goes beyond the original palindrome with center $c$.
$c={i}^{%u2032},r={i}^{%u2032}+p\left[{i}^{%u2032}\right]$ as the next expanding will be around center ${i}^{%u2032}$.

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;
}
----------------------------------------
Output:
7
omaramo #### More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 163 0
C++ Sieve Of Erastosthenes 136 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 286 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 121 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 92 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 200 0
C++ Smallest window with all characters in string 94 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 70 0
C++ Number of Bracket Reversals needed to make expression Balanced 73 0
C++ String to Palindrome with Append Function 84 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 75 0
C++ Search String in Grid 84 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 115 0
C++ String Matching(KMP Algorithm) 141 0
C++ Remove Duplicates From String 111 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 87 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 91 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 291 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 329 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 365 0
C++ Greedy Approach Prims MST 399 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 334 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 349 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2