chevron_left
399 points
8 4 3

 A function to find out the longest palindrome in a given string

Example for finding the longest palindrome with proper explanation below given example:

palindrome is a word, phrase, or sentence that reads the same backward or forward--such as Madam, I'm Adam. Semordnilaps (the word palindromes in reverse) are words that spell other words when spelled backward (for example, star/rats, drawer/reward).

We can find the longest palindrome substring in (n^2) time with O(1) extra space. 
 

  1. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
  2. To generate odd length palindrome, Fix a center and expand in both directions for longer palindromes, i.e. fix i (index) as a center and two indices as i1 = i+1 and i2 = i-1
  3. Compare i1 and i2 if equal then decrease i2 and increase i1 and find the maximum length. 
    Use a similar technique to find the even-length palindrome.
  4. Take two indices i1 = i and i2 = i-1 and compare characters at i1 and i2 and find the maximum length till all pair of compared characters are equal and store the maximum length.
  5. Print the maximum length.

The function is a logic by which we can implement this logic on any given string to find out the longest palindrome


// A O(n^2) time and O(1) space program to
// find the longest palindromic substring
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to print
// a substring str[low..high]
void printSubStr(char* str, int low, int high)
{
    for (int i = low; i <= high; ++i)
        cout << str[i];
}
 
// This function prints the
// longest palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
int longestPalSubstr(char* str)
{
    // The result (length of LPS)
    int maxLength = 1;
 
    int start = 0;
    int len = strlen(str);
 
    int low, high;
 
    // One by one consider every
    // character as center point of
    // even and length palindromes
    for (int i = 1; i < len; ++i) {
        // Find the longest even length palindrome
        // with center points as i-1 and i.
        low = i - 1;
        high = i;
        while (low >= 0 && high < len
               && str[low] == str[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            --low;
            ++high;
        }
 
        // Find the longest odd length
        // palindrome with center point as i
        low = i - 1;
        high = i + 1;
        while (low >= 0 && high < len
               && str[low] == str[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            --low;
            ++high;
        }
    }
 
    cout << "Longest palindrome substring is: ";
    printSubStr(str, start, start + maxLength - 1);
 
    return maxLength;
}
 
// Driver program to test above functions
int main()
{
    char str[] = "vanillaicecreamisfun";
    cout << "\nLength is: "
         << longestPalSubstr(str)
         << endl;
    return 0;
}
 

More Posts

How to find longest palindrome in a string in java Sanjana Sagar - May 22
How to find all permutations of a string in Java Hasnain_khan - Oct 13, 2020
find a word in a string python SharadMagar450 - Aug 7
Longest substring without repeating characters javascript Sanjana Sagar - May 19
Find the largest palindrome in a given string hhh98hd - Aug 3
C program to replace a word in a string without using function Sanjana Sagar - May 20
How to find the longest word in a string JavaScript sakshi - May 26
A statement that is true both forwards and backwards Huzaifa-Glitch - Jun 25
The fastest method to search for files in the Linux directory tree is to use the ____ command. sakshi - Sep 11
How to print a function in python amna - Jun 29