C++ Manachars Algorithm














































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(N2) 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(N3).

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(N2). For example: given string is "czbza", when b is selected as the center, it produces the longest palindromic substring "zbz".

However, O(N2) 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 NS = "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=[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 rl,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[i]%u2264r%u2212i%u2032),

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

(2) Else p[i%u2032]%u2265p[i],

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

Let d=distancer%u2212i%u2032, so expanding around center i%u2032 will start from (i%u2032%u2212d)%u22121 with (i%u2032+d)+1=(r+1) and so on... because the interval [i%u2032%u2212d:i%u2032+d] 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(N).

(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[i%u2032] 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

Comments