跨 2 个字符串的 C++ 搜索模式而不连接它们

Question

我有:

std::string b;
std::string p;
const std::string sep;

b是缓冲区，p是数据包(新到达的字节)，sep是分隔符序列，例如\r\n\r\n。我想在 b + p 中找到下一次出现分隔符的位置，然后将范围 p.begin(), pos 从 p 移动到 b 没有必要地增加 b。如果没有找到 sep，只需追加所有内容。从逻辑上讲，它看起来像这样:

std::string cc = b + p;
auto cc_pos = std::search(cc.begin(), cc.end(), sep.begin(), sep.end());
b = std::string(cc.begin(), atcc);
if (b.size() > MAX_BYTES) 
     throw std::runtime_error("packet too large");
if (cc_pos != cc.end())
    p = std::string(cc_pos + sep.size(), cc.end());
else
    p.clear();

但是我在这里创建了临时的 cc，它的大小为 p.size() + b.size()。如何高效地(不分配堆内存)并且尽可能优雅地做到这一点？字符串 b 保留了 MAX_BYTES，因此插入速度很快，但它不应分配超过此数量。

Answer 1

如果我没理解错的话，你可以搜索b的最后n个字符其中 n 是 sep 的长度.如果发现 sep 序列从 b 的最后 n 个字符开始sep的第二部分可以在p开头搜索.

有点像

int n = sep.size();
int remaining = n;

for (int i = 0; i < sep.size(); i++) {
    /* Search for entire sep at end of b
        if not found, search for sep minus last char
        then minus last 2 chars, 3 chars, and so on
    */
    auto it = std::search(b.end() - n - i, b.end(), sep.begin(), sep.end() - i);
    if (it != b.end()) {
        remaining = i; // number of sep chars to search for in p
        break;
    }
}

if (remaining > 0) {
    std::string sep_sub = sep.substr(n-remaining, remaining);
    std::string p_sub = p.substr(0, remaining);

    if (sep_sub == p_sub) {
        // Found sep split across b and p!
    }
}

这应该检查 sep 的出现吐对面b和 p无需连接。唯一使用的额外内存是 sep_sub和 p_sub合并后的大小最多为 2 * (sizeof(sep) - 1) .

这只检查 sep 是否被 b 和 p 分割。您仍然需要检查整个 sep 是否不在 b 或 p 中。