Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time.

Find the longest palindromic substring of a given string.

Naive Approach

In naive or brute approach, we would consider each position in string S as a possible center of palindrome and then find the longest palindrome by considering it as a centre.Finally we output, maximum length palindrome.The time complexity of this approach is O(n*n).

1. result = -1
2. maxlength = 0
3. for i in range(2*n + 1):
4.     for j in range(1,n):
5.         if (i//2-j)<0 or (i//2+j)>=n or S[i//2-j] != S[i//2+j]: 
6.                break
7.         elif i%2 == 0 and 2*j > maxlength:
8.                maxlength = 2*j
9.                result = i
10.        elif i%2 == 1 and 2*j+1 > maxlength:
11.               maxlength = 2*j + 1
12.               result = i

Efficient Algorithm

The main idea behind the efficient approach is that in brute force we have to iterate over each character to find the longest palindrome corresponding to each position as a centre but now we will use longest palindromes around previous centre to find longest palindromes around new upcoming centres.I am dividing Manacher's Algorithm in two parts for better understanding:-

1. Finding longest odd length palindromic substring.
2. Finding longest even length palindromic substring.
I am going to explain manacher's algorithm for odd length longest palindromic string and then very easily modify string to find even length palindromic substring with same algorithm.

Longest odd length palindromic Substring

First I will give you an idea behind algorithm and then we will discuss all cases which can possible.Before starting anything I just want you to keep that whenever I wrote LPS it represent Longest Palindromic Substring around any centre. Consider a string "abacabad" and following analysis:-

Index:  0 1 2 3 4 5 6 7
String: a b a c a b a d
LPS:    1 3 1 7 1 3 1 1
Note that: Here LPS[i] represent length of longest palindromic substring if i is considerd as centre of palindrome.

In above example, in any palindromic substring, Right half substrings are mirror image of left half, and also the corresponding right half of LPS array is also mirror image of corresponding left half. For example:- "abacaba" is one of the palindromic substrings which can found above and its LPS corresponding each position is 1 3 1 7 1 3 1 and this is also symmetric about index 3 of string. This is happening because as right half of palindromic string is mirror image of left half, so same mirror image of palindromes founded in left half may be present in right half. The reason behind using maybe is following situtaions:-
1. First case: Consider below example:

Index:  0 1 2 3 4 5 6 7
String: a b a c a b a c
LPS:    1 3 1 7 1 5 1 1

Here, Notice that palindrome of length 7 can be found around index 3 and according to that LPS around index 5 and index 1 must be same but here LPS around index 5 is 5 instead of 3. The reason behind is the scope of palindrome around index 7 starts at index 0 and ends at index 6 and palindrome around index 5 according to mirror concept must be 3 within parent palindrome scope but here palindrome of length 3 around index 5 ends at same index 6, so here are chances that the characters outside parent palindrome scope may be added to increse the length of palindrome around index 5.
Conclusion: This is happening because child palindrome is reaching to right end of parent palindrome but here length of child palindrome cannot be less than the corresponding value in left half of parent palindrome(in above case length of child palindrome is atleast 3).

2. Second case:
Consider below example:

Index:  0 1 2 3 4 5 6 7 8
String: c a b a c a b a x
LPS:    1 1 5 1 7 1 3 1 1

In above examle I just reverse the string (used in case 1) and append 'x' to generate just opposite case. Here LPS value at index 6 must be 5 according to index 2 and parent palindrome around index 4 but here also problem is of scope. Here the scope of palindrome around index 4 starts from index 1 but the scope of palindrome around index 2 is starting from index 0. That's why when we saw right half of palindrome around index 4, we found that the palindrome around index 6 cannot go further of rightend of parent palindrome(i.e index 7) which gives value of LPS only 3.
Conclusion: When child palindrome's right end is going further of right end of parent palindrome then child palindrome can go maximum to the right end of parent palindrome(here right end is at index 7).

Algorithm

Lets, consider we found LPS of a i^th index by a iterating over each character one by one and say we found length of longest palindrome LPS[i] starting from index li and ending at index ri. And note that currently i^th index is centre of focus or in other words palindrome starting from index li and ending at index ri is parent palindrome in focus and now we will find all child palindromes around each position of its right half.
This parent palindrome or centre of focus will change when we will find next index around which palindrome exist of such length that its right end (or ri^' ) is greater than ri of current centre of focus. Lets consider predicted LPS for j^th index is x and according to it li^' and ri^' are index of left end and right end respectively of predicted palindrome according mirror image in parent palindrome. Now following three cases can be generated:
Case 1 (When ri^' == ri):
This happens when parent palindrome's right end and child palindrome's right end are equal than this become same special case 1 we discussed above, now we try to expand it more by comparing next characters with its mirror.In this case centre of focus changes to current index j or in other words child palindrome become parent palindrome.
Case 2 (When ri^' > ri):
This happens when parent palindrome's right end is less than child palindrome's right end than this become same special case 2 we discussed above. In this case Predicted value of LPS is greater than actual and its actual value corresponds child palindrome right end to ri instead of ri^'as we discussed above. Hence actual value of LPS[j] is 2*(ri - j)+1 because right end is at ri and j is its centre of child palindrome about which we are discussing.
Case 3 (When ri^' < ri): This happens when parent palindrome's right end is greater than child palindrome's right end than this become normal case.In this case predicted LPS[i] is correct because child palindrome is fully contined in parent palindrome.

Longest even length palindromic Substring

To find longest even length palindromic substring we are going to use exact same algorithm which we have discussed above for odd length palindrome but before applying that algorithm we modify string. For example consider below example:

 1. Let us we have string s = "abaab". Note that here longest 
    palindrome is "baab" of length 4.
 
 2. Then we construct a modified string s1 = "$a$b$a$a$b$".
 
 3. Now we apply algorithm to find longest odd length palindrome in this 
    modified string s1 which give us an longest odd length 
    palindromic substring which is "$b$a$a$b$" of length 9.
    
 4. Now just remove all '$' sign from palindrome and we will get 
    our longest even length palindrome. 
    For example "$b$a$a$b$" --> "baab".

Complexity

Time Complexity:O(n)
Space Complexity: O(n)

Implementation

#include <bits/stdc++.h>
using namespace std;
vector <int> createLPS(string s)
{
	vector <int> LPS(s.size(), 1);
	int i, j, ri = 0, li = 0, centre = 0;
	/* li stores starting position of parent palindrome
	   ri stores end position of parent palindrome
	   centre stores the index of element around which palindrome exists
	*/
	for(i=1; i < s.size(); i++)
	{
		if(i <= ri)
		{
			LPS[i] = LPS[centre - (i-centre)];
			if((i+ (LPS[i]-1)/2) > ri) // Case2 condition
				LPS[i] = 2 *(ri- i) + 1;
			else if((i+ (LPS[i]-1)/2) == ri) // Case 1 condition
			{
				j = (LPS[i]-1)/2 + 1;
				while((i+j) < s.size() && (i-j)>= 0 && s[i+j]==s[i-j])
					j++;
				j--;
				LPS[i] = 2*j +1;
				centre= i;
				li= i- j;
				ri= i+ j; 
			}
		}
		else
		{
           /*When index i for which we are calculating LPS is not inside parent palindrome.*/
			j=1;
			while((i+j) < s.size() && (i-j)>= 0 && s[i+j]==s[i-j])
					j++;
				j--;
				LPS[i] = 2*j +1;
				centre= i;
				li= i- j;
				ri= i+ j;
		}

	}
	return LPS;
}

int main()
{
	string s, s1="$";
	cin >> s;
	pair< int, int> ans = make_pair(0, 1); 
	//ans pair stores size of longest palindrome and index of first character of longest palindrom
	
	////
	vector<int> LPS = createLPS(s);
	for(int i=0; i < LPS.size(); i++)
	{
		if(LPS[i] > ans.first)
		{
			ans.first = LPS[i];
			ans.second = i - (LPS[i]-1)/2;
		}
	}
	////////////// Above calculation is for finding longest Odd length palindrome

	/////////////
	for(int i =0; i < s.size(); i++)
	{
		// This loop appends $ sign in each gap of string (E.g: s = absana -->  s1= $a$b$s$a$n$a$)
		s1.push_back(s[i]);
		s1.push_back('$');
	}
	LPS = createLPS(s1);
	for(int i=0; i < LPS.size(); i++)
	{
		if((LPS[i]-1)/2 > ans.first)
		{
			ans.first = (LPS[i]-1)/2;
			ans.second = (i - (LPS[i]-1)/2)/2;
		}
	}
	/////////////Above calculation is for finding longest Even length palindrome

	cout << "Longest palindrome length is " << ans.first << " and it is started from index :" << ans.second; 
}

Application

1. Manacher's algorithm is used to find longest palindromic substring in linear time complexity.