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建議您要粘貼的功能，其中它被稱爲編譯程序，而不是調用函數。函數調用減慢了程序的執行速度。