Getting a wrong answer for SPOJ PLD

Question

I am trying to solve problem PLD on SPOJ, but I'm getting a WA on the 9th testcase.

My Approach:
I am implementing Manacher's Algorithm and I believe that if something wrong is there, then it can be wrong in this code.

if((k%2==0)&&(p[i]>=k)&&(temp[i]=='#'))
                                       count++;
if((k%2==1)&&(p[i]>=k)&&(temp[i]!='#'))
                                       count++;

But according to my approach if character is #, then the maximum length of palindromic string centered at it can be even only, so if p[i] >= k, then I am increasing count if we are finding a palindromic string of even length.

Similarly for characters [considering input character i.e other than #] centered at i-th location but for odd length strings.

#include<stdio.h>
#include<string.h>
char a[30002],temp[60010];
int p[60010];
int min(int a,int b)
{
    if(a<b)
           return a;
    return b;
}
int main()
{
    //freopen("input.txt","r+",stdin);
    //freopen("a.txt","w+",stdout);
    
    int k,len,z;
    scanf("%d",&k);
    getchar();
    gets(a);
    len=strlen(a);
    
    //Coverting String
    temp[0]='$';
    temp[1]='#';
    z=2;
    for(int i=1;i<=len;i++)
    {
            temp[z++]=a[i-1];
            temp[z++]='#';
    }
    len=z;
    int r=0,c=0,check=0,idash,t,count=0;
    for(int i=1;i<len;i++)
    {
            check=0;
            idash=c-(i-c);
            p[i]=r>i?min(r-i,p[idash]):0;
            
            t=p[i];
            while(temp[i+p[i]+1]==temp[i-1-p[i]])
                                                p[i]++;
            
            if(r<i+p[i])
            {
                        c=i;
                        r=i+p[i];
            }
            if((k%2==0)&&(p[i]>=k)&&(temp[i]=='#'))
                                                   count++;
            if((k%2==1)&&(p[i]>=k)&&(temp[i]!='#'))
                                                  count++;
    }
    
    printf("%d",count);
    //getchar();
    //getchar();    
    return 0;
}

Answer 1

You may want to take advantage of C++ short-circuit evaluation of logical expressions.
For example, rearrange the order so you check for '#' first:

if ((temp[i] == '#') && (k % 2 == 0) && (p[i] >= k))  

In the above rearrangement, if the character is not '#', none of the other expressions are evaluated.

You may want to extract (p[i] >= k) to an outside if statement since it is common to both:

if (p[i] >= k)
{
  if ((temp[i] == '#') && (k % 2 == 0)) ++count;
  if ((temp[i] != '#') && (k % 2 == 1)) ++count;
}

The above modification will result in only one evaluation of the expression (p[i] >= k).

Also examine your for loop to see if there are statements or expressions that don't change or are repeated. If a statement or expression doesn't change inside the loop, it is called an invariant, and can be moved before or after the loop.

Statements or expressions that are duplicated (such as array index calculations) can be evaluated and stored in a temporary variable. Although good compilers may do this (depending on the optimization level), in your performance requirements, you may want to help out the compiler.

Another suggestion is to replace p[i] with a pointer to the location or a reference to the location. Again, this is to help out the compiler when the optimization is not set optimally:

  int& p_slot_i = p[i];  // This syntax needs checking
// or
  int * p_slot_i = &p[i];
//...
  t = *p_slot_i;
  while(temp[i + *p_slot_i + 1] == temp[i - 1 - *p_slot_i)
  {
    *p_slot_i++;
  }

Lastly, Elimination of spaces, blank lines and curly braces DOES NOT AFFECT PROGRAM PERFORMANCE. A program that is one line or spaced across multiply lines will have the exact assembly translation and the exact performance. So please, add spaces, blank lines and curly braces to improve readability.

Edit 1: performance of min()
You may want to declare you min() function as inline to suggest to the compiler you want the function pasted where it is called, rather than calling the function. Function calls slow down a programs execution.