Tuesday, July 10, 2012

Write a program to find the longest palindrome in a string

The approach:-
  1. From each character location, compare the left and right locations for equality.

  2. Remember the location and maximum size of equality.

  3. Print the string starting from the location minus maximum size to location plus maximum size, which is the longest palindrome.

C++ program to find the longest palindrome in a string

#include <iostream>
#include <cstring>
using namespace std;

int main() {
   char input[] = "jsdfjdsfhracecarksdfjsdkfmalayalamcheck";
   char* ptr = input;

   int location = 0;
   int maxsize = 0;
   for ( int i = 0; i < strlen(input) - 1; i++ ) {
       int left = i;
       int right = i;
       int count = 0;
       while ( left > 0 ) {
           if ( input[left--] != input[right++] ) {
               break;
           }
           count++;
       }
       if ( count > maxsize ) {
          maxsize = count;
          location = i;
       }
   }

   cout << maxsize << " @ " << location << endl;
   int start = location - maxsize;
   int end = location + maxsize;
   for ( int i = start + 1; i < end; i++ ) {
       cout << input[i];
   }
   return 0;
}

Output:-
5 @ 29
malayalam

Contact Form

Name

Email *

Message *

Back to Top