Thursday 24 May 2012

Find Longest Palindrome in a string : O(n*n) C code

  Given a string S, find the longest palindromic substring in S.


For example,
S = “caba".
The longest palindromic substring is “aba”.

Algorithm:
  1. Palindrome mirrors around center and there are 2N-1 such centers in string. The reason is center of palindrome can be in between two letters(for even length string) or the letter itself (for odd length string).
  2. Expand a palindrome around its center in both direction and look for maximum possible palindrome (O(n) time).
  3. If the length of string is odd, the center would be letter, therefore repeat the step 2 for each letter and update maximum palindrome on the way.
  4. If the length of string is even, the center would be between two letters, therefore repeat the step 2 for each such center and update the maximum palindrome on the way.
  5. Since there are O(N) such centers, time complexity would be O(n2).

// O(n*n) time complexity and O(1) space algorithm
#include<stdio.h>
#include<string.h>

void longestpalindrome(char *str);

int main()
{
char *str = "abacba";
int i;
longestpalindrome(str);
scanf("%d", &i);
}

void longestpalindrome(char *str) {

int length = strlen(str);
printf("%d\n", length);
int i,j,k;
int start,end,max=0,curr;

if(length == 0) {printf("string null"); return;}

if(length%2!=0) { //if string is of odd length
    for(i=0;i<length-1;i++) {
        j=k=i;
        while(j>0 && k<length-1 && str[--j]==str[++k]); 
        curr = k-j+1;
        if(curr > max) {
           max = curr;
           start = j;
           end = k;
        }
    }
    for(i=start;i<=end;i++) printf("%c", str[i]);
    printf("\n");
}
else { //if string is of even length
    for(i=0;i<length-1;i++) {
        if(str[i]==str[i+1]) {
            j=i;
            k=i+1;
            while(j>=0 && k<=length-1 && str[j--]==str[k++]);
                    curr = k-j-1;
                    if(max < curr) {
                       max = curr;
                       start = j+1;
                       end = k-1;
                    }
        }
        for(i=start;i<=end;i++) printf("%c", str[i]);
        printf("\n");
    }
}
}
  
                         
       
   

// Time Complexity: O(n2)

// Space Complexity: O(1)                          

        

1 comment:

  1. There are some bugs in your code... for example

    For even sized strings, you are assuming the longest palindrome will always have a center formed of 2 letters... take your example
    abacba the longest palindrome there is "aba"... but your algorithm will try to find a str[i]==str[i+1] and will never find it...


    One possible fix, could be, search the whole string for two-letters centered palindromes... and then look again the string for single-letter centered palindrome... and get the longest one...

    ReplyDelete