SPOJ PLD [错误的答案]

Question

我正在努力解决problem PLD on SPOJ，但我在第九个测试案例中获得了WA。

我的方法：
我正在实施Manacher的算法，我相信如果出现错误，那么在代码中可能会出错。

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

但根据我的方法，如果角色是#，则集中在它可以甚至只有回文字符串的最大长度，所以如果p[i] >= k，那么我增加数量，如果我们发现甚至回文串长度。

类似的字符[考虑输入字符，但不是＃]集中在第i个位置，但奇数长度的字符串。请帮助....

#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

您可能需要采取C++ 短路优势的逻辑表达式评价。
例如，重新排列的顺序，以便你检查“＃”第一：

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

在上述重排，如果字符不是“＃”，没有任何其它表达式的求值。

你可能要提取(p[i] >= k)到外部if声明，因为它是常见的两种：

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

上述修改将导致只有一个表达(p[i] >= k)的评价。

还要检查您的for循环以查看是否有不更改或重复的语句或表达式。如果语句或表达式在循环内没有更改，则称其为不变量，并且可以在循环之前或之后移动。

重复的语句或表达式（例如数组索引计算）可被评估并存储在一个临时变量中。尽管优秀的编译器可能会这样做（取决于优化级别），但在您的性能要求中，您可能需要帮助编译器。

另一个建议是用指向该位置的指针或对位置的引用替换p[i]。再次，这是助阵编译时没有设置优化最佳：

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

最后，消除空格，空行和大括号不影响方案执行。一行或多行间隔的程序将具有精确的汇编转换和确切的性能。因此，请添加空格，空行和花括号以提高可读性。

编辑1：最小的性能（）
您可能要宣告你min()功能inline建议您要粘贴的功能，其中它被称为编译程序，而不是调用函数。函数调用减慢了程序的执行速度。