1

私は、部分文字列をテキストに一致させるためにこの Morris-Pratt アルゴリズムに取り組んできましたが、コンパイラが文句を言わないように、実際の関数で失敗関数を宣言する方法に問題があります。これを終わらせるのに2時間ほどかかります。だからすぐに私を助けてください:/

int KMPmatch(const string& text, const string& pattern)
{
  int n = text.size();
  int m = pattern.size();
  std::vector<int> fail = computeFailFunction(pattern);
  int i = 0;
  int j = 0;

  while (i < n)
  {
    if (pattern[j] == text[i])
    {
      if (j == m-1) return i-m+1;
      i++; j++;
    }
    else if (j > 0) j = fail[j-1];
    else i++;
  }

  return -1;
}

//KMPFailure function
std::vector<int> computeFailFunction(const string& pattern)
{
  std::vector <int> fail(pattern.size());
  fail[0] = 0;
  int m = pattern.size();
  int j = 0;
  int i = 1;

  while (i < m)
  {
    if (pattern[j] == pattern[i])
    {
      fail[i] = j+1;
      i++; j++;
    }
    else if (j > 0)
    {
      j = fail [j-1];
    }
    else
    {
      fail[i]= 0;
      i++;
    }
  }

  return fail;
}
4

1 に答える 1

0

std::vector<int> computeFailFunction(const string& pattern);の前に 置きint KMPmatch(const string& text, const string& pattern)ます。

または、関数宣言をヘッダー ファイルに入れ、ソース ファイルにインクルードします。これは、複数のソース ファイルを持つプロジェクトが行うことです。

于 2013-09-09T01:46:43.880 に答える