c - KNP字符串匹配算法有什么问题？

我已经根据Wikipedia中的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。我从另一本书;-)中获得了表构建思想，验证了它确实给出了与Wiki中匹配的正确结果。

上面的代码现在已针对每个人的利益进行了纠正（根据Michael的回答）。我已将我的错误（以注释形式）放入此处，因此引起了问题。

最佳答案

您在抄录中打了错字：

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

应该：

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

我还建议您从循环中删除对strlen(pattern)的调用，并在循环开始之前调用一次。

关于c - KNP字符串匹配算法有什么问题？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16757637/