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字符串匹配算法：辅助阵列输出

回答

相关问题