Manacher's Algorithm
Manacher's algorithm is used to find the longest palindromic substring in a given string. A palindrome is a string that is equal to its reverse and a palindromic substring is a substring of a string that is also a palindrome, such as "aabaa" in "aabaaccaabaa". This algorithm was proposed by Glenn K. Manacher in the year 1975.
How Manacher's Algorithm works?
The naive approach to finding the longest palindromic substring is to check every possible substring of the given string and then verify whether it is a palindrome or not. However, this would consume more time and space.
The Manacher's Algorithm solves this problem in linear time, i.e. O(n), by using some observations and tricks. The main idea is to use the symmetry property of palindromes to avoid unnecessary comparisons.
Algorithm
The following steps are involved in the Manacher's Algorithm −
First, we preprocess the given string by inserting a special character, such as '#' between every pair of characters and at the beginning and end of the string. This ensures that every palindrome in the new string has an odd length and a unique centre. For example, the string "abba" becomes "#a#b#b#a#".
Next, we create an array named P[] of the same length as the new string, where P[i] stores the length of the longest palindromic substring centred at position i in the new string. We initialize P[0] = 0 and P[1] = 1, since the first two characters are always single-character palindromes.
Then, we iterate over the new string from left to right.
For each position i, find the mirror position j of i with respect to the center of the current rightmost palindrome.
Next, copy the value of P[j] to P[i], unless it exceeds the boundary R.
Expand the palindrome centred at i by comparing the characters on both sides of i + P[i]. If they match, we increment P[i] by 1 and repeat this step until they do not match or we reach the ends of the string.
Example
In the following example, we will practically demonstrate how Manacher's algorithm works in various programming languages.
#include<stdio.h>
#include<string.h>
// Function to return the minimum of two integers
int minm(int a, int b) {
return (a<b)?a:b;
}
// Function to find longest palindromic substring
void findLongPalindrome(char orgnlString[]) {
int n = strlen(orgnlString);
if(n == 0)
// If the string is empty, return an empty string
return;
n = 2*n + 1;
// Array to store the length of palindrome
int lenPalndrm[n];
// Initialization of first two positions
lenPalndrm[0] = 0; lenPalndrm[1] = 1;
int centerIndex = 1;
int rightIndex = 2;
int right = 0, left;
int maxPalLength = 0, maxCenterIndex = 0;
int start = -1, end = -1, diff = -1;
// Loop through the string
for (right = 2; right < n; right++) {
left = 2*centerIndex-right;
lenPalndrm[right] = 0;
diff = rightIndex - right;
// If difference is greater than 0, update length at current position
if(diff > 0)
lenPalndrm[right] = minm(lenPalndrm[left], diff);
// While the palindrome can be extended, extend it
while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
(orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
lenPalndrm[right]++;
}
// If the palindrome length at the current position is greater than the maximum palindrome length, update the maximum palindrome length and its center index
if(lenPalndrm[right] > maxPalLength) {
maxPalLength = lenPalndrm[right];
maxCenterIndex = right;
}
// If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
if (right + lenPalndrm[right] > rightIndex) {
centerIndex = right;
rightIndex = right + lenPalndrm[right];
}
}
start = (maxCenterIndex - maxPalLength)/2;
end = start + maxPalLength - 1;
// maximum palindrome
char maxPalindrm[end-start+2];
strncpy(maxPalindrm, &orgnlString[start], end-start+1);
maxPalindrm[end-start+1] = '\0';
printf("Longest palindrome is: %s
", maxPalindrm);
}
int main() {
char orgnlString[] = "AAAABCAEAAABCBDDAAAAABC";
// method calling
findLongPalindrome(orgnlString);
return 0;
}
#include<iostream>
using namespace std;
// Function to return the minimum of two integers
int minm(int a, int b) {
return (a<b)?a:b;
}
// Function to find longest palindromic substring
string findLongPalindrome(string orgnlString) {
int n = orgnlString.size();
if(n == 0)
// If the string is empty, return an empty string
return "";
n = 2*n + 1;
// Array to store the length of palindrome
int lenPalndrm[n];
// Initialization of first two positions
lenPalndrm[0] = 0; lenPalndrm[1] = 1;
int centerIndex = 1;
int rightIndex = 2;
// Variables to store the current right and left positions
int right = 0, left;
// Variables to store maximum palindrome length and its center index
int maxPalLength = 0, maxCenterIndex = 0;
int start = -1, end = -1, diff = -1;
// Loop through the string
for (right = 2; right < n; right++) {
// Calculate the corresponding left position
left = 2*centerIndex-right;
lenPalndrm[right] = 0;
diff = rightIndex - right;
// If difference is greater than 0, update length at current position
if(diff > 0)
lenPalndrm[right] = min(lenPalndrm[left], diff);
// While the palindrome can be extended, extend it
while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
(orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
lenPalndrm[right]++;
}
// If the palindrome length at the current position is greater than the maximum palindrome length, update the maximum palindrome length and its center index
if(lenPalndrm[right] > maxPalLength) {
maxPalLength = lenPalndrm[right];
maxCenterIndex = right;
}
// If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
if (right + lenPalndrm[right] > rightIndex) {
centerIndex = right;
rightIndex = right + lenPalndrm[right];
}
}
// Calculate the start and end indices of the maximum palindrome
start = (maxCenterIndex - maxPalLength)/2;
end = start + maxPalLength - 1;
string maxPalindrm;
// Construct the maximum palindrome
for(int i=start; i<=end; i++)
maxPalindrm += orgnlString[i];
// Returning maximum palindrome
return maxPalindrm;
}
int main(int argc, char *argv[]) {
string orgnlString, palindrome;
orgnlString = "AAAABCAEAAABCBDDAAAAABC";
// method calling
palindrome = findLongPalindrome(orgnlString);
cout << "Longest palindrome is: " << palindrome << endl;
}
import java.util.Arrays;
public class Main {
// Function to find longest palindromic substring
public static String findLongestPalindrome(String orgnlString) {
// If the string is null or empty, return an empty string
if (orgnlString == null || orgnlString.length() == 0)
return "";
char[] s2 = addBoundaries(orgnlString.toCharArray());
// Array to store the length of palindrome
int[] lenPlandrm = new int[s2.length];
int centerIndex = 0, right = 0;
// to compare if two elements are the same
int m = 0, n = 0;
// Loop through the string
for (int i = 1; i<s2.length; i++) {
if (i > right) {
lenPlandrm[i] = 0; m = i - 1; n = i + 1;
} else {
int i2 = centerIndex * 2 - i;
if (lenPlandrm[i2] < (right - i - 1)) {
lenPlandrm[i] = lenPlandrm[i2];
m = -1;
} else {
lenPlandrm[i] = right - i;
n = right + 1; m = i * 2 - n;
}
}
// While the palindrome can be extended, extend it
while (m >= 0 && n < s2.length && s2[m] == s2[n]) {
lenPlandrm[i]++; m--; n++;
}
// If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
if ((i + lenPlandrm[i]) > right) {
centerIndex = i; right = i + lenPlandrm[i];
}
}
int len = 0; centerIndex = 0;
// Find the maximum palindrome length and its center index
for (int i = 1; i<s2.length; i++) {
if (len < lenPlandrm[i]) {
len = lenPlandrm[i]; centerIndex = i;
}
}
// Construct the maximum palindrome
char[] maxPalindrm = Arrays.copyOfRange(s2, centerIndex - len, centerIndex + len + 1);
// Returning maximum palindrome
return String.valueOf(removeBoundaries(maxPalindrm));
}
// Function to add boundaries to handle even length palindromes
private static char[] addBoundaries(char[] cs) {
if (cs == null || cs.length == 0)
return "||".toCharArray();
char[] cs2 = new char[cs.length * 2 + 1];
for (int i = 0; i < (cs2.length - 1); i = i + 2) {
cs2[i] = '|';
cs2[i + 1] = cs[i / 2];
}
cs2[cs2.length - 1] = '|';
return cs2;
}
// Function to remove the added boundaries from the result
private static char[] removeBoundaries(char[] cs) {
if (cs == null || cs.length < 3)
return "".toCharArray();
char[] cs2 = new char[(cs.length - 1) / 2];
for (int i = 0; i < cs2.length; i++) {
cs2[i] = cs[i * 2 + 1];
}
return cs2;
}
public static void main(String[] args) {
String orgnlString = "AAAABCAEAAABCBDDAAAAABC";
System.out.println("Longest palindrome is: " + findLongestPalindrome(orgnlString));
}
}
def add_boundaries(cs):
if cs is None or len(cs) == 0:
return ['|', '|']
cs2 = ['|'] * (len(cs) * 2 + 1)
for i in range(len(cs)):
cs2[i * 2 + 1] = cs[i]
return cs2
def remove_boundaries(cs):
if cs is None or len(cs) < 3:
return ""
cs2 = [''] * ((len(cs) - 1) // 2)
for i in range(len(cs2)):
cs2[i] = cs[i * 2 + 1]
return ''.join(cs2)
def find_longest_palindrome(orgnl_string):
if orgnl_string is None or len(orgnl_string) == 0:
return ""
s2 = add_boundaries(list(orgnl_string))
len_palandrm = [0] * len(s2)
center_index = 0
right = 0
m = 0
n = 0
for i in range(1, len(s2)):
if i > right:
len_palandrm[i] = 0
m = i - 1
n = i + 1
else:
i2 = center_index * 2 - i
if len_palandrm[i2] < (right - i - 1):
len_palandrm[i] = len_palandrm[i2]
m = -1
else:
len_palandrm[i] = right - i
n = right + 1
m = i * 2 - n
while m >= 0 and n < len(s2) and s2[m] == s2[n]:
len_palandrm[i] += 1
m -= 1
n += 1
if (i + len_palandrm[i]) > right:
center_index = i
right = i + len_palandrm[i]
length = 0
center_index = 0
for i in range(1, len(s2)):
if length < len_palandrm[i]:
length = len_palandrm[i]
center_index = i
max_palindrm = s2[center_index - length : center_index + length + 1]
return remove_boundaries(max_palindrm)
orgnl_string = "AAAABCAEAAABCBDDAAAAABC"
print("Longest palindrome is:", find_longest_palindrome(orgnl_string))
Output
Longest palindrome is: AAAAA
