c++ - 在Blob中找到最长的Blob前缀

我尝试针对以下问题在C ++中产生/获取有效的实现：

我必须blob（const char *数据，size_t长度），我称它们为“ blob1”和“ blob2”。现在我想在“ blob1”中获得最长的“ blob2”前缀。如果最长的前缀在“ blob1”中是多次，我喜欢得到索引最大的那个。

这是一个示例（blob此处只是ASCII字符串，因此更易于阅读示例）：

blob1 = HELLO LOOO HELOO LOOO LOO JU

blob2 = LOOO TUS

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

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

blob2中blob1的最长前缀是LOOO。它在那里两次：
HELLO *LOOO *HELOO *LOOO *LOO JU

所以我想获得第二个索引，即6，前缀的长度为4。

不幸的是blob1和blob2改变了很多次，因此创建树或其他复杂结构的过程可能很慢。

您知道解决此问题的好算法吗？

谢谢。

干杯
凯文

最佳答案

我不知道这是否是解决此问题的最佳算法（我敢肯定，不是），但是，我想这是一个很好的算法。这个想法很简单，首先从blob1中的blob2搜索最低的令牌开始。找到匹配项后，尝试查看是否可以在此位置匹配更大的令牌。如果是这样，请更新令牌长度。

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

贝娄是一个简单的磁通图，试图解释该算法，并依次显示一个简单的完整程序，显示了一种实现。

#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;

}

关于c++ - 在Blob中找到最长的Blob前缀，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19526968/