Checking if a string is a palindrome

Question

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?

• JS1: How did you measure the times? Have you considered that 0.0018 seconds could be in the margin of error for your time measurement?
• Verbatim: Your second example uses void main -- always use int main.
• chux: @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?"
• Verbatim: @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.

Answer 1

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;
}

• Toby Speight: Good answer; you might want to point out that scanf("%s", &buf) also has an overflow problem, fixable with "%*s", sizeof buf - 1, &buf.
• Felix Palmen: Good catch, I didn't have a closer look at the second example.
• Felix Palmen: @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...
• Toby Speight: 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?
• Felix Palmen: @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.

Answer 2

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.

About code review in itself:

• 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).

Answer 3

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.