0

我已经根据维基百科中 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 中匹配的正确结果。

为了大家的利益，现在更正了上面的代码（根据迈克尔的回答）。我已经提出了我的错误（以注释掉的形式），因此问题被放在这里。

4

1 回答 1

1

您在转录中打错了字：

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

应该：

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

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

于 2013-05-26T09:18:48.813 回答