0

次のKMP実装があります：

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

int kmp(char substr[], char str[])
{
   int i, j, N, M;

   N = strlen(str);
   M = strlen(substr);

   int *d = (int*)malloc(M * sizeof(int));
   d[0] = 0;

   for(i = 0, j = 0; i < M; i++)
   {
      while(j > 0 && substr[j] != substr[i])
      {
         j = d[j - 1];
      }

      if(substr[j] == substr[i])
      {
         j++;
         d[i] = j;
      }
   }

   for(i = 0, j = 0; i < N; i++)
   {
      while(j > 0 && substr[j] != str[i])
      {
         j = d[j - 1];
      }

      if(substr[j] == str[i])
      {
         j++;
      }

      if(j == M)
      {
         free(d);
         return i - j + 1;
      }
   }

   free(d);

   return -1;
}

int main(void)
{
   char substr[] = "World",
      str[] = "Hello World!";

   int pos = kmp(substr, str);

   printf("position starts at: %i\r\n", pos);

   return 0;
}

ここでテストできます：http：//liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80

それは小さな文字列でうまく機能します、そして私はそれを大きなループでテストしました、この方法ですべてがうまくいきます。

しかし、検索している部分文字列と完全な文字列を次のように変更すると、次のようになります。

char substr[] = "%end%",
str[] = "<h1>The result is: <%lua% oleg = { x = 0xa }
         table.insert(oleg, y) oleg.y = 5 print(oleg.y) %end%></h1>";

最初の試行の後、この実装は失敗します...

アルゴリズムを文字列内のそのようなデータで機能させるために、KMPの実装を修復するのを手伝っていただけませんか...

4

1 に答える 1

2

ソースから逸脱した 1 つの場所で、ソースには

while(j>0 && p[j]!=p[i]) j = d[j-1];
    if(p[j]==p[i])
        j++;
        d[i]=j;

あなたが持っている間

while(j > 0 && substr[j] != substr[i])
{
    j = d[j - 1];
}
if(substr[j] == substr[i])
{
    j++;
    d[i] = j;
}

ソースのインデントにだまされています。if()ソースでは、ブランチを囲む中括弧がないため、インクリメントのみが;j++;によって制御されます。無条件です。ifd[i] = j;

次に、おそらくインデックスの異常な使用が原因で、ソースにエラーがあります。アレイをセットアップする正しい方法は次のとおりです。

int *d = (int*)malloc(M * sizeof(int));
d[0] = 0;

for(i = 1, j = 0; i < M; i++)
{
    while(j > 0 && substr[j-1] != substr[i-1])
    {
        j = d[j - 1];
    }

    if(substr[j] == substr[i])
        j++;
    d[i] = j;
}

しかし、ここでの設定ではインデックスi-1とおよびインデックスを使用j-1しiてjを決定するため、混乱しますd[i]。それを実装する通常の方法は異なります。C#での実装方法。これはほとんどの情報源で見られる形式であるため、その正確性を自分自身に納得させるのははるかに簡単です.

于 2012-06-29T10:07:52.073 に答える