KMP字符串匹配算法：輔助陣列輸出

這是我執行KMP字符串匹配算法。當我檢查pi陣列，它存儲0,1,2,3,4,5,6。但根據算法書它應該是0,0,1,2,3,0,1。我的代碼也給出了正確的結果。我不明白爲什麼會發生這種情況，或者我做錯了什麼？如果是這樣，請糾正我。KMP字符串匹配算法：輔助陣列輸出

謝謝。

#include<iostream> 
#include<string> 
#include<string.h> 

using namespace std; 

int* ComputePrefix(char P[]) 
{ 
    size_t m = strlen(P); 
    int *pi = new int[m]; 
    pi[0] = 0; 
    int k = 0; 

    for(int q =0; q < m; q++) 
    { 
     if(k > 0 && P[k+1] != P[q]) 
      k = pi[k]; 

     if(P[k+1] == P[q]) 
      { 
       pi[q] = k; 
       k = k + 1; 
      } 
      pi[q]=k; 
    } 

    return (pi); 
} 

void KMP_Matcher(char T[], char P[]) 
{ 

    size_t n = strlen(T); 
    size_t m = strlen(P); 

    int *pi = new int[m]; 
    pi = ComputePrefix(P); 

    cout<<endl; 


    int q =0; 
    for (int i = 0; i <= n; i++) 
    { 
     if(q > 0 && P[q] != T[i]) 
     { 
      q = pi[q - 1]; 
     } 


     else if(P[q] == T[i]) 
     { 


      if(q == m-1) 
      { 
       cout<<"Shift occurs at : "<< i-q <<endl; 
       q = pi[q]; 
      } 
      else q = q + 1; 
     } 

     else q++; 
    } 
} 


int main() 
{ 
    char T[] = "abababacaba"; 
    char P[] = "ababaca"; 

    KMP_Matcher(T,P); 
    return 0; 
}

來源

2012-03-26 IndieProgrammer

您的跳轉表構造函數根本不檢查針的前綴。我們希望能夠查找，在針的每個位置，最長可能適當的前綴針導致高達（但不包括）該位置，比全前綴其他的長度開始needle[0]，只是未能匹配;這是我們在尋找下一場比賽時需要走多遠。因此，跳轉表中的每個條目（例如，table[i]）恰好是最長可能的針前綴的長度，該前綴也是以needle[i - 1]結尾的子串的前綴。

跳轉表中的前兩個條目是-1和0，因爲a）模式開始處的不匹配不會觸發回溯（或換句話說，零長度的前綴不能有任何適當的前綴或後綴）和b）空字符串被認爲是長度爲0.

有關更多詳細信息，請參閱wikipedia或算法教科書。

上面完成的代碼是：

int *build_jump_table(const char * target) 
{ 
    if(!target) 
     return NULL; 
    int *table = new int[strlen(target) + 1]; 
    if(!table) 
     return NULL; 
    table[0] = -1; /* unused by the matcher, just used here */ 

    for(int i = 0; target[i] != '\0'; i++) { 
     table[i+1] = table[i] + 1; 
     while(table[i+1] > 0 && target[i] != target[table[i+1] - 1]) { 
      table[i + 1] = table[table[i + 1] - 1] + 1; 
     } 
    } 
    return table; 
}

這是相當冗長，當你理解了跳轉表背後的概念可以簡化很多。

來源

2012-03-26 12:36:04

KMP字符串匹配算法：輔助陣列輸出

回答

相關問題