這個KNP字符串匹配算法有什麼問題？

我已經寫了KNP的基礎上的維基百科的僞代碼KNP 這個KNP字符串匹配算法有什麼問題？

但不幸的是，它似乎並沒有給出正確的結果。

#include <stdio.h> 
#include <stdlib.h> 

void getNext(char *p, int next[]) 
{ 
    int i, j; 
    int m = strlen(p); 
    next[0] = -1; 

    for(j=1; j<m; j++) 
    { 
    i = next[j - 1]; 
    while((i >= 0) && (p[j - 1] != p[i])) 
    { 
     i = next[i]; 
    } 
    next[j] = i+1; 
    } 
} 

int knp(char *text, char* pattern, int T[]) 
{ 
    int m = 0; // The beginning of the current match in text 
    int i = 0; // The position of the current character in W 

    int pattern_length = strlen(pattern) - 1; 

    while(m+i < pattern_length) 
    { 
    if(pattern[i] == text[m+i]) // Made a mistake here and wrote: text[m] 
     { 
     if(i ==) 
     { 
       return m; 
      } 
      else 
       i = i + 1; 
     } 
     else 
     { 
      if(T[i] > -1) 
       i = T[i]; 
      else 
       i = 0; 

      m = m + i - T[i]; 
     } 
    } 
    return -1; // If we reach here, the string is not found 
} 
int main() 
{ 
    int next[7]; 
    int i; 
    char *ptr = "ababaca"; 
    char *text = "ababbababaaaababacaacd"; 

    getNext(ptr, next); 
    for(i=0; i<7; i++) 
    { 
    printf("%d\t",next[i]); 
    } 
    printf("\n"); 

    printf("Pattern match at: %d",knp(text, ptr, next)); 
}

注意：只有KNP取自wiki。我從另一本書中獲取的表格構建理念;-)，驗證它確實給出了與維基中相匹配的正確結果。

上面的代碼現在已經糾正（根據邁克爾的答案），爲大家的利益。我已經把我的錯誤（在註釋表格中），因爲這裏提出了這個問題。

來源

2013-05-26 kingsmasher1

使用調試器並完成您的工作。 –

@MichaWiedenmann：如果調試所有問題都很容易，像stackoverflow這樣的網站將不會存在。此外，我不告訴任何人調試我的代碼。這個是公開在維基上的，預計很多人可能會在我之前使用它。如果有人已經完成了我的要求。最糟糕的是，我的面試日期太近了。 – kingsmasher1

你期待什麼結果，你看到了什麼？這可能會被視爲「不是真正的問題」。 – xaxxon

你已經在你的轉錄做了一個錯字：

if(pattern[i] == text[i])

應該是：

if(pattern[i] == text[m + i])

我還建議你從內刪除調用strlen(pattern)您循環並在循環開始之前調用一次。

來源

2013-05-26 09:18:48 Michael

非常感謝，這很好。 – kingsmasher1

這個KNP字符串匹配算法有什麼問題？

回答

相關問題