# A Quick Guide to Manacher's Algorithm

## Overview

Manacher’s algorithm is a string-matching algorithm that is used to find the longest palindromic substring in a given string. It was developed by Michael O. Rabin and Richard M. Karp in 1975 and later improved by G. Manacher in 1979.

## Concept

Palindromic strings are strings that read the same forward and backward. For example, “racecar” is a palindromic string because it is spelled the same forwards and backward. Finding the longest palindromic substring in a given string is an important problem in computer science because it has numerous applications, such as spell checkers, text editors, and DNA sequence analysis.

The basic idea behind Manacher’s algorithm is to use a dynamic programming approach to find the longest palindromic substring efficiently. It does this by maintaining a table of the lengths of the palindromic substrings centered at each character in the string.

## Algorithm

• First, we need to preprocess the string by adding special characters between each pair of characters in the string. This is done to ensure that all palindromic substrings have an odd length.
• Next, we create a table to store the lengths of the palindromic substrings centered at each character in the string.
• We then iterate through the string and, for each character, we compute the length of the longest palindromic substring centered at that character using the values in the table.
• To compute the length of the palindromic substring centered at a given character, we first initialize the value in the table to be 1. We then check the characters on either side of the current character to see if they are the same. If they are, we increment the value in the table and continue checking until we reach a character that is not the same or we reach the end of the string.
• We repeat this process for each character in the string, and the final result is the longest palindromic substring in the string.
• Finally, we need to find the longest palindromic substring in the string. We can do this by comparing the values in the table and returning the substring with the maximum length.

## Implementation

 #include #include using namespace std;// Function to preprocess the string by adding special characters between// each pair of charactersstring preprocess(string s){    // Add a special character at the beginning and end of the string    s = "^" + s + "\$";    // Insert a special character between each pair of characters    for (int i = 1; i < s.length() - 1; i += 2)        s.insert(i, "#");    return s;}// Function to find the longest palindromic substring using Manacher's algorithmstring manacher(string s){    // Preprocess the string    s = preprocess(s);    // Create a table to store the lengths of the palindromic substrings    // centered at each character    int n = s.length();    int table[n];    // Initialize the table to all zeros    for (int i = 0; i < n; i++)        table[i] = 0;    // Initialize variables to store the center and rightmost point of the    // palindromic substring    int center = 0;    int right = 0;    // Iterate through the string    for (int i = 1; i < n - 1; i++)    {        // Find the mirrored index of the current character        int mirror = 2 * center - i;        // If the current character is within the palindromic substring        // centered at the center, use the mirrored value from the table        if (i < right)            table[i] = min(right - i, table[mirror]);        // Expand the palindromic substring centered at the current character        // by checking the characters on either side        while (s[i + 1 + table[i]] == s[i - 1 - table[i]])            table[i]++;        // Update the center and rightmost point of the palindromic substring        // if necessary        if (i + table[i] > right)        {            center = i;            right = i + table[i];        }    }    // Find the maximum value in the table    int maxLength = 0;    int centerIndex = 0;    for (int i = 1; i < n - 1; i++)    {        if (table[i] > maxLength)        {            maxLength = table[i];            centerIndex = i;        }    }    // Extract the longest palindromic substring from the original string    int start = (centerIndex - maxLength) / 2;    return s.substr(start, maxLength);}int main(){    // Test Manacher's algorithm on a sample string    string s = "abcba";    cout << manacher(s) << endl;    return 0}
write your code here: Coding Playground

## Time Complexity

Manacher’s algorithm has a time complexity of O(n), which makes it much faster than other string-matching algorithms that have a time complexity of O(n^2) or higher. It is also relatively simple to implement, making it a popular choice for finding the longest palindromic substring in a given string.

One potential drawback of Manacher’s algorithm is that it requires preprocessing the input string by adding special characters between each pair of characters. This can increase the space complexity of the algorithm and make it less efficient for very large strings.

Despite this, Manacher’s algorithm remains a powerful and efficient tool for finding the longest palindromic substring in a given string. It has numerous applications in various fields, including spell checkers, text editors, and DNA sequence analysis.

## Summary

Manacher’s algorithm is a dynamic programming approach to finding the longest palindromic substring in a given string. It has a time complexity of O(n) and is relatively simple to implement, making it a popular choice for solving this problem. While it does require preprocessing the input string, its efficiency and effectiveness make it a valuable tool in many applications.