A Quick Guide to Manacher's Algorithm

Board Infinity
Board Infinity
A Quick Guide to Manacher's Algorithm

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search 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 <iostream>

#include <string>


using namespace std;


// Function to preprocess the string by adding special characters between

// each pair of characters

string 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 algorithm

string 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.