# Palindrome Checker Algorithm

Here is an example of how I solved this problem (though this is not the only nor the best way by any means) for an assignment where it was also requisite to determine if a string was a reverse prefix of the other. Obviously a palindrome is a reverse prefix of itself so if you can determine a reverse prefix then you can determine a palindrome.

I would love some feedback on my code as well as any thoughts on my implementation/solution.

int main()
{
char string1[50];
char string2[50];

printf("Please enter a string: ");
gets(string1);
if (strlen(string1) == 1)
exit(1);
printf("Please enter a second string: ");
gets(string2);
printf("\nString 1 = %s", string1);
printf("\nString 2 = %s\n", string2);
if (isReversePrefix(string1, string2))
printf("String 2 is a reversed prefix of string 1\n");
if (isPalindrome(string1))
printf("String 1 is a palindrome\n");
else
printf("String 1 is not a palindrome\n");
if (isPalindrome(string2))
printf("String 2 is a palindrome\n");
else
printf("String 2 is not a palindrome\n");
return 0;
}
/************************************************
isReversePrefix - Receives two string pointers
and determines if the second is a reverse
prefix of the first. Returns either true or
false.
The word 'HIM' has the following prefixes 'H', 'HI',
'HIM'. All of these can be reversed to 'H', 'IH', 'MIH'
************************************************/
int isReversePrefix(char *str1, char *str2)
{
char *temp1 = str1;
char *temp2 = str2;

if (strlen(str2) > strlen(str1))
return 0;

strrev(temp2);
while ((*temp1 == *temp2) && (*temp2 != '\0'))
{
temp1++;
temp2++;
}
if (*temp2 == '\0')
return 1;
else
return 0;
}
/************************************************
isPalindrome - receives one string parameter and
checks if it is a palindrome or not. Returns
true if it is and false if not.
************************************************/
int isPalindrome(char *str1)
{
char *start = str1;
char *end = str1 + strlen(str1) - 1;
if (isReversePrefix(start, end))
return 1;
else
return 0;
}

• str2.strlen()??? what kind of C code is this? I'm having a hard time believing this compiles... – glampert Dec 1 '14 at 3:56
• If you are using all string functions, why not strcmp to reduce your code :) – thepace Dec 1 '14 at 6:27
• thepace: Your suggestion is 100% correct. If I remember correctly the assignment prohibited us from using strcmp because a requirement and code not included in this post was to write our own version of comparing two strings. – aus_lacy Dec 1 '14 at 15:27
• glampert: I edited the code from the original copy/paste and was in the OOP dot notation frame of mind rather than the STL strlen(char*) frame of mind. Major goof up on my part. Above code is edited. – aus_lacy Dec 1 '14 at 16:13
• Still has temp2.strrev();. – ferada Dec 1 '14 at 16:19

• Since the char array sizes are fixed, you should make sure the inputs are of an appropriate size before continuing. This should best be done with the function doing the reading.

Very important: gets() is unsafe as it has no knowledge of buffer size thus is vulnerable to buffer overflow. Instead, use fgets(), which is safer as it takes a buffer size as an argument.

• Consider hard-coding the 50 to make its intent clear.

#define MAX_LENGTH 50

• Since you're already in main(), you can use return 1 instead of exit(1).

• Unformatted strings like this:

printf("Please enter a string: ");


can instead be output using puts():

puts("Please enter a string: ");


Be aware that puts() automatically appends a newline at the end. If you don't want this newline, then you can use fputs() instead:

fputs("Please enter a string: ", stdout);

1. These functions should be able to handle constant arrays.

// int isReversePrefix(char *str1, char *str2)
int isReversePrefix(const char *str1, const char *str2)

2. By calling strlen(str2) > strlen(str1), code is marching down each string twice. Only need to find the end of one.

int isReversePrefix(const char *str1, const char *str2) {
const char *p2 = str2[strlen(str2)];

while (*str1 && p2 > str2) {
p2--;
if (*str1 != *p2) {
return 0;
}
str1++;
}

return *str1 == '\0' && p2 == str2;
}

3. Now that isReversePrefix() handles constant strings, isPalindrome() is easy:

int isPalindrome(char *str1) {
return isReversePrefix(str1, str1);
}

4. Original isPalindrome() has 2 problems: Consider what happens when str1 == ""

char *end = str1 + strlen(str1) - 1;
if (isReversePrefix(start, end))

5. Calling isReversePrefix() with isReversePrefix(start, end) simple will not work. The code is only checking if the first char of the string matches its end.

6. Original isReversePrefix() reverses the contents of str2. This may be an very unhappy side effect for an application calling isReversePrefix()

7. An efficient re-write of isPalindrome() would find the length and then do length/2 compares.