Palindrome is a string which when divided into two halves reflects itself. An example of a Palindrome is as follows: abcddcba. To identify an palindrome proves to be an important work item in Genetic engineering. For more information on this check Biological Structures.
Ok Now in our today’s topic we might want to come up with an effecient algorithm to verify if the given string is a palindrome or not.
I have just written a small program in C++ that does the same. Instead of the usual one by one comparison, this algo uses a determinent to form an intelligent binary search that would return an invalid palindrome as soon as possible. Meaning, to validate a string to be a paindrome we need to obviously traverse the whole of the characters in the string only then we can confirm efectively its a palindrome. But in my new algorithm my goal is to detect an invalid palindrome as quickly as possible so that we can save some computing time to check the next string for a palindrome.
Take a look at this algorithm that i have devised for this: Please do not use this algo for any of your personal or official purpose as i dont guarantee or confer any warranty for the code below. If you are planning to use any of the code snippet below, you would want to mail me first and get my consent and permission before doing so.
int main(int argc, char* argv[])
{
char *string = “abcdefghijklmn0pqrrqp0nmlkjihgfedcba”;
size_t length= strlen(string);
if( length % 2 != 0)
{
printf(”Not a Palindrome \n”);
return 0;
}
char *ptr1=string; //Start
char *ptr3 =(string +length -1);
// I would like to name the following algorithm as Aravinthan’s Palindrome Algorithm.//Determinent is the Highest 2^(N-1) which can divide N.
// EG: Determinent(D) of 24 characters would be 8*3=24=N (2^3 *3) so determinent shall be 2^(3-1)= 4.
// This would give us 4 groups of six elements each, that can be compared simultaneouly.
// This optimizes the space by four times.
// though this algo gives anasymtotic notation of O(N/2) as the worst case.
// Happens if the invalid entry of the palindrome is on the last element in a group or
// Happens if the total no of elements by mod 4 is greater than 0.
// The best case optimization shall be
// when the invalid entry(e) is found where (e)<Dth position in a group
// Efficiency increases as (e) approaches towards the first group and towards the first element in the group.
// In that case Efficiency would be O(D) where D is guranteed to be < N/2.
// The efficiency(Eff) of this algorithm lies between
//O(D) < (Eff) <O(N/2) as (e) approaches last group or last element of any group.
int determinent=1;
while(true)
{
determinent *= 2;
if(length % determinent >0)
{determinent /=2;
break;}
}
if(length ==determinent)
{determinent /=2;
}
if(determinent ==2)
{
length /=2;
determinent /=2;
}
for(int index=0;index<determinent;index++)
{
for(int step=0;step<(length/(determinent));step++)
{
if(*(ptr1+index+(step*(determinent))) != *(ptr3-index-(step*(determinent))))
{
printf(”%s is not a Palindrome.\n”,string);
return 0;
}
}
}
printf(”String %s is a Palindrome”,string);return 0;
}
