0

我尝试在 C++ 中为以下问题生成/获得有效的实现:

我必须 blob(const char *data,size_t 长度),我称它们为“blob1”和“blob2”。现在我想在“blob1”中获得最长的“blob2”前缀。如果最长的前缀在“blob1”中多次出现,我希望得到具有最大索引的前缀。

这是一个示例(此处的 blob 只是 ASCII 字符串,因此更易于阅读示例):

斑点1 =HELLO LOOO HELOO LOOO LOO JU

斑点2 =LOOO TUS

以下是 blob2 的所有有效前缀:

{ L, LO, LOO, LOOO, LOOO, LOOO T, LOOO TU, LOOO TUS}

blob2in的最长前缀blob1LOOO. 它有两次: HELLO *LOOO *HELOO *LOOO *LOO JU

所以我想得到第二个的索引,这将是6,以及前缀的长度是4.

不幸的是,blob1 和 blob2 多次更改,因此创建树或其他一些复杂结构可能很慢。

你知道解决这个问题的好算法吗?

谢谢你。

干杯凯文

4

1 回答 1

1

我不知道这是否是解决这个问题的最佳算法(我敢肯定,这不是),但是,我想这是一个很好的算法。这个想法很简单,首先从 blob1 中的 blob2 中搜索最低标记。当您找到匹配项时,请尝试查看您是否可以在此位置匹配更大的标记。如果这是真的,请更新您的令牌长度。

从最后一站继续搜索,但此时,从 blob2 中搜索具有更新令牌长度的令牌。当您找到匹配项时,请尝试查看您是否可以在此位置匹配更大的标记。如果这是真的,请更新您的令牌长度。重复前面的过程,直到缓冲区结束。

Bellow 是一个简单的通量图,试图解释这个算法,并依次是一个简单的完整程序,展示了一个实现。

在此处输入图像描述

#include <algorithm>
#include <vector>
#include <iostream>

/////////////////////0123456789012345678901234567
const char str1[] = "HELLO LOOO HELOO LOOO LOO JU";
const char str2[] = "LOOO TUS";

int main()
{
  std::vector<char> blob1(strlen(str1));
  std::vector<char> blob2(strlen(str2));
  blob1.reserve(30);
  blob2.reserve(30);

  std::copy(str1, str1+strlen(str1), blob1.begin());
  std::copy(str2, str2+strlen(str2), blob2.begin());

  auto next = blob1.begin();
  auto tokenLength = 1;
  auto position = -1;

  while ( std::next(next, tokenLength) < blob1.end() ) {
    auto current = std::search(next, 
                               blob1.end(), 
                               blob2.begin(), 
                               std::next(blob2.begin(), tokenLength));

    if (current == blob1.end() )
      break;

    position = std::distance(blob1.begin(), current);
    next = std::next(current, 1);

    for (auto i = tokenLength; std::next(blob2.begin(), i) < blob2.end(); ++i) {
      auto x = std::search(std::next(current, i), 
                           std::next(current, i + 1), 
                           std::next(blob2.begin(), i), 
                           std::next(blob2.begin(), i + 1));
      if ( x != std::next(current, i) ) 
            break;

      ++tokenLength;
    }
  }

  std::cout << "Index: " << position << ", length: " << tokenLength << std::endl;

}
于 2013-10-22T23:12:54.670 回答