Friday, August 11, 2006

Longest Palindrome

Write a program which finds the longest palindrome in a given string of characters.
/******
Assumption1.
===========
So if it were of even length then the centre would be i and i+1 for example
KaaK
0123
so centers are 1,2
but for a odd length palindrome the centers are one and the same as in
KapaK
01234
so centers are 2,2

Assumption2:
============
If two strings have the same center and smaller one is not a palindrome then bigger can't be a palindrome

for example:abcddeba
index willb:01234567
since str[3,4] is a palindrome then [2,5] may be a palindrome
but since str[2,5] is not a palindrome [1,6] can't become palindrome.

Logic:
======
Here i take every index in the array as the center of the palindrome.
Now first loop searches for odd lenght palindromes in the string.
Taking the first 0,0 as the centers we try to expand our palindrome till we
encounter the boundaries or a mismatch. In such a way we can eliminate all
the strings with the same base which are not palindromes.

******/

void longestPalindrome(char *input)
{
int len;
int i=0,j=0,k=0,l=0;
int lower=0,upper=0;
len = strlen(input);

/*Odd length Palindromes*/
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

/*Even length Palindromes*/
i = 0;
j = 1;
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

for(i=lower;i lessThan =upper;i++)
{
printf("%c",input[i]);
}
printf("\n");
}

3 comments:

Anonymous said...

dsalgo.blogspot.com; You saved my day again.

aravind646 said...

Tis is working fr
input[]={'b','a','b','c','b','a'};

aravind646 said...

Tis is NOT working fr
input[]={'b','a','b','c','b','a'};