我不知道这是否是解决这个问题的最佳算法(我敢肯定,这不是),但是,我想这是一个很好的算法。这个想法很简单,首先从 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;
}