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

2 comments :

  1. waht if there is a subtring such as 'maddam' ?
    i doubt if this wil detct maddam as the longet palindrome if 'malayalam'from this example is excluded..

    ReplyDelete
  2. The above solution is good and a nice attempt to solve .

    as mentioned in the abaove comment , for madam , it will fail ..

    the best and most optimum solution is using suffix tree ,

    please see the link

    http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree

    there are off course other lot of stuff about suffix tree and longest palindrome in net .

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top