# Checking if a string is a palindrome

This is the code for checking if a string is a palindrome. The execution time, for sample cases, is 0.40358 seconds. What must be done to increase the performance?

int main(){
int c,flag = 0;
char *ch, *h;
ch = (char *)malloc(sizeof(char)*101);
h = ch;
while((c=getchar())!=EOF){
*ch = c;
ch++;
}
ch--;
while(ch>=h){
if(*ch-- != *h++){flag = 1; break;}
}
flag == 1?(printf("NO")):(printf("YES"));
}


This is the code with an execution time of 0.4017 seconds for same test cases:

void main()
{
char a[100],b[1000];
int n,i,j=0,f=0;
scanf("%s",a);
n=strlen(a);
for(i=n-1;i>=0;i--)
{
b[j]=a[i];
j++;
}
for(i=0;i<n-1;i++)
{
if(a[i]==b[i])
{
f++;

}
}
if(f==n-1)
{
printf("YES");
}
else
{
printf("NO");
}
}


Why is the former slower than the latter? Are the library functions faster?

• How did you measure the times? Have you considered that 0.0018 seconds could be in the margin of error for your time measurement? – JS1 Jun 6 '17 at 8:18
• Your second example uses void main -- always use int main. – ringzero Jun 7 '17 at 15:38
• @ringzero "always use int main. " --> C specifies that an implementation is allowed other main() signatures. It is doubtful that changing the signature affects OP's goal of "What must be done to increase the performance?" – chux - Reinstate Monica Jun 9 '17 at 2:54
• @chux Posting a program on CodeReview invites comments about any aspect of the code. A program which uses void main -- rather than int main -- is of questionable quality. The OP's concern about speed is perhaps misplaced considering the well-known advice: first make it work, then make it right and finally make it fast. – ringzero Jun 9 '17 at 17:47

The first version is the better approach and as already pointed out, what you measure here is outside the precision of measuring, so performance-wise, these solutions are equal.

Now some suggestions how to improve the code of the first version:

• You allocate your buffer in a needlessly complicated way:

ch = (char *)malloc(sizeof(char)*101);


first of all, there's no point of casting void * in C, it is implicitly convertible to any data pointer type. Casting it could even hide a bug, see this stackoverflow answer for details. Then, sizeof(char) is defined to be 1, so you can leave it out. The whole line would then look like:

ch = malloc(101);


But why should you use dynamic allocation at all if you use a fixed size? Just use an array, similar to the code in your second version:

char buf[101];


Note I also suggest a different name here: buf tells the reader that this is a buffer for something (input in your case), while ch would make you think it's the name of a variable holding a single character.

• You happily overflow your buffer:

while((c=getchar())!=EOF){
*ch = c;
ch++;
}


You should never write code like this. There are functions for reading a limited amount of data, and as your buffer has a fixed size, you should use such a function, e.g.:

memset(buf, 0, 101);
size_t n = fread(buf, 1, 101, stdin);
char *ch = buf + n;


Without knowing your exact requirements, I guess you didn't intend to analyze "multi-line" palindromes, so using fgets() would be even a better choice:

if (!(fgets(buf, 101, stdin) && *buf)) exit(1);
size_t n = strlen(buf);
if (buf[n-1] == '\n') buf[--n] = 0; // strip newline if present
char *ch = buf + n;


This is still close to your initial code, in practice, I'd use a larger buffer just to be sure and also define the buffer size as a macro, so I can change it without risking to introduce an overflow bug.

• Regarding your second version, using scanf("%s", ...) will also overflow any buffer. A safe way of using scanf for reading in a fixed size buffer would be scanf("%100s", buf) if buf has a size of 101. I'd suggest not to use scanf() for this purpose at all. -- thanks for the comment!

• A minor point since you are interested in performance:

    flag == 1?(printf("NO")):(printf("YES"));


printf() must scan its first argument to know whether there are more arguments to follow, this is unnecessary for a constant output, so just use puts() if you want an automatic newline or fputs() to avoid the newline. In this case, puts() will be fine:

    flag == 1?(puts("NO")):(puts("YES"));

• And as a general advise: Try to find better variable names that really describe the meaning of the variable, like instead of a flag, how about a isPalindrome?

Suggested improved version which also improves on readability:

#include <stdio.h>
#include <string.h>

#define BUFSIZE 1024
char buf[BUFSIZE]; // 1K buffer with static storage

int main(void)
{
if (!(fgets(buf, BUFSIZE, stdin) && *buf))
{
// reading a line from stdin failed, give up
return 1;
}

size_t n = strlen(buf);
if (buf[n-1] == '\n') buf[--n] = 0; // strip newline

char *front = buf;
char *back = buf + n;

int isPalindrome = 1;
while (back > front)
{
if (*--back != *front++)
{
isPalindrome = 0;
break;
}
}

puts(isPalindrome ? "YES" : "NO");
return 0;
}

• Good answer; you might want to point out that scanf("%s", &buf) also has an overflow problem, fixable with "%*s", sizeof buf - 1, &buf. – Toby Speight Jun 6 '17 at 15:40
• Good catch, I didn't have a closer look at the second example. – Felix Palmen Jun 6 '17 at 15:52
• @TobySpeight but I don't think a * would work as expected, as I read the scanf() manual, this just discards the result of the conversion... – Felix Palmen Jun 6 '17 at 16:10
• I was thinking of printf() where the * says that the field width is to come from arguments. Sorry about that! There's a bit of a dance to get safe scanf(): How to prevent scanf causing a buffer overflow in C? – Toby Speight Jun 6 '17 at 17:08
• @chux forget my complaint about your first comment, you probably meant stdin could actually deliver a 0 byte, yes, that's true, so I'm adding a little check here. – Felix Palmen Jun 9 '17 at 6:27

You can't really call a difference of 1% slower or faster. You should consider that both codes have exactly the same performance.

The only explanation for a speed difference between those two applications comes from the malloc (which is slightly slower than an array).

IMO, first code is better than second; the second one is quite hard to get (you are basically reversing a string, then comparing the reversed string with the normal one). I actually had to read the code 3 times to understand what was done.

• First code sample:

You should indent your code in a consistent manner.

int c,flag = 0;
char *ch, *h;


Those variables are poorly named; flag could be replaced by is_palindromic, h could be string_start/str_start/str, and ch string_from_end/string_reverse etc....

while((c=getchar())!=EOF){


It's usually a good idea to separate comparators and equal sign from their operands, so it'd be something like this:

while((c = getchar()) != EOF){

• Second code sample:

char a[100],b[1000];
int n,i,j=0,f=0;


Same as before, you should also avoid declaring 4 variables on the same line (especially considering you have both initialized and non-initialized variables).

You are comparing all the characters of two the arrays:

for(i=0;i<n-1;i++)
{
if(a[i]==b[i])
{
f++;

}
}


Instead, you can do something like this :

isPalin = 0 ;
n= strlen(charArray)
for(i=0;i<n/2;i++)
{
if( charArray[i] != charArray[j] )
{
isPalin = 1 ;
break ;
}
j-- ;
}
puts(isPalin? "YES" : "NO" ) ;


You only use one array and only traverse till (n/2-1) position of the array compared to your example. Execution time comes down to 0.822 secs.