Coders Packet

Longest Palindromic Substring/Manachar's Algorithm in C++

By srijan bharadwaj

In this tutorial, we will know how to find the Longest Palindromic Substring in a string using Manachar's Algorithm.

The longest Palindromic Substring can be used to find solutions to many big problems.

We can use these methods to solve the following problem which is to find the longest palindromic substring in a string:-

1.Brute Force - Using two loops and find all the palindromes of the substring and compare and find the maximum of all the substrings.

2. Dynamic Programming -  Find the Longest Common Subsequence between the string and reverse of the given string.

3. Manachar's Algorithm - Finding the center index of the string and print out the substring. We will discuss more about this here... 

Manachar's Algorithm

Assume a String S of length N. We have to create a String of length 2N+1, by adding letters that are not already present in the string

Let's take an example and see how this Algorithm works:-

Let S="abababa" and we add special characters to it to make it lets say "#a#b#a#b#a#b#a#".

Now we take another array let's call it P[]. We have to expand around every character in the new string and find the center index which will have the maximum value the above-given example will give P=[0,1,0,3,0,5,0,7,0,5,0,3,0,1,0], So as we can see around 7 the strings are repeating so we use this to find the substring we need.

Stepwise Explanation of the Algorithm:-

1.We have to take two pointers center(c) and right(r) to keep track if the palindrome expands after r (or the original palindrome).

2.We fill the P array by expanding every character in the new string.

3.We update the position of c and r if it expands after r.

4. We then find the Maximum Value of the P array and we save its index (in Max Palindrome and Center Index variable )respectively.

5.We Find the substring and return it.

Note- We divide it by 2 because at the center the palindrome is repeated.

Hence, we find the longest palindromic substring using manachar's algorithm.

Download Complete Code


No comments yet