我正在构建一个用于字符串匹配的简单多服务器。我通过使用套接字和选择同时处理多个客户端。服务器所做的唯一工作是:客户端连接到服务器并通过网络套接字将针(大小小于 10 GB)和大海捞针(任意大小)作为流发送。针和干草堆是任意二进制数据。

服务器需要在大海捞针中搜索所有出现的针(作为精确的字符串匹配)并将一些针匹配发送回客户端。服务器需要即时处理客户端并能够在合理的时间内处理任何输入(即搜索算法必须具有线性时间复杂度)。

要做到这一点，我显然需要将大海捞针分成一小部分(可能比针小)，以便在它们通过网络套接字时处理它们。也就是说，我需要一个能够处理字符串的搜索算法，该字符串被分成多个部分并在其中进行搜索，就像 strstr(...) 一样。

我找不到任何标准的 C 或 C++ 库函数，也找不到可以按部分处理字符串的 Boost 库对象。如果我没记错的话，strstr()、string.find() 和 Boost searching/knuth_morris_pratt.hpp 中的算法只能在整个 haystack 位于连续的内存块中时处理搜索。还是有一些技巧可以用来按缺少的部分搜索字符串？你们知道任何 C/C++ 库，能够应对如此大的针头和干草堆吗？能够处理 haystack 流或在 haystack 中按部分搜索？

我没有通过谷歌搜索找到任何有用的库，因此我被迫创建自己的 Knuth Morris Pratt 算法变体，它能够记住自己的状态(如下所示)。然而，我并不认为它是最佳解决方案，因为在我看来，经过良好调优的字符串搜索算法肯定会表现得更好，而且以后的调试也不会那么担心。

所以我的问题是: 除了创建我自己的搜索算法之外，是否有一些更优雅的方法可以按部分在大型 haystack 流中进行搜索？有什么技巧可以为此使用标准的 C 字符串库吗？是否有一些专门用于此类任务的 C/C++ 库？

这是我的中间 KMP 算法的(部分)代码:

#include <cstdlib>
#include <cstring>
#include <cstdio>

class knuth_morris_pratt {
    const char* const needle;
    const size_t needle_len;
    const int* const lps; // a longest proper suffix table (skip table)

// suffix_len is an ofset of a longest haystack_part suffix matching with
// some prefix of the needle. suffix_len myst be shorter than needle_len.
// Ofset is defined as a last matching character in a needle.
    size_t suffix_len;
    size_t match_count; // a number of needles found in haystack

public:
    inline knuth_morris_pratt(const char* needle, size_t len) : 
            needle(needle), needle_len(len),
            lps( build_lps_array() ), suffix_len(0),
            match_count(len == 0 ? 1 : 0)    {  }
    inline ~knuth_morris_pratt() {  free((void*)lps);   }

    void search_part(const char* haystack_part, size_t hp_len); // processes a given part of the haystack stream
    inline size_t get_match_count() { return match_count; }

private:
    const int* build_lps_array();
};

// Worst case complexity: linear space, linear time

// see: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
// see article: KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R., 1977, Fast pattern matching in strings
void knuth_morris_pratt::search_part(const char* haystack_part, size_t hp_len) {
    if(needle_len == 0) {
        match_count += hp_len;
        return;
    }

    const char* hs = haystack_part;

    size_t i = 0; // index for txt[]
    size_t j = suffix_len; // index for pat[]
    while (i < hp_len) {
        if (needle[j] == hs[i]) {
            j++;
            i++;
        }

        if (j == needle_len) {
            // a needle found
            match_count++;
            j = lps[j - 1];
        }
        else if (i < hp_len && needle[j] != hs[i]) {
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }

    suffix_len = j;
}

const int* knuth_morris_pratt::build_lps_array() {
    int* const new_lps = (int*)malloc(needle_len);
//    check_cond_fatal(new_lps != NULL, "Unable to alocate memory in knuth_morris_pratt(..)");

    // length of the previous longest prefix suffix
    size_t len = 0;
    new_lps[0] = 0; // lps[0] is always 0

    // the loop calculates lps[i] for i = 1 to M-1
    size_t i = 1;
    while (i < needle_len) {
        if (needle[i] == needle[len]) {
            len++;
            new_lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = new_lps[len - 1];

                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                new_lps[i] = 0;
                i++;
            }
        }
    }

    return new_lps;
}


int main() 
{
    const char* needle = "lorem";
    const char* p1 = "sit voluptatem accusantium doloremque laudantium qui dolo";
    const char* p2 = "rem ipsum quia dolor sit amet";
    const char* p3 = "dolorem eum fugiat quo voluptas nulla pariatur?";
    knuth_morris_pratt searcher(needle, strlen(needle));
    searcher.search_part(p1, strlen(p1));
    searcher.search_part(p2, strlen(p2));
    searcher.search_part(p3, strlen(p3));

    printf("%d \n", (int)searcher.get_match_count());

    return 0;
}

最佳答案

你可以看看BNDM ，与 KMP 具有相同的性能:

• O(m) 用于预处理
• O(n) 匹配。

用于nrgrep ，可以找到其来源here其中包含 C 源代码。

BNDM 算法的 C 源是here .

参见 here获取更多信息。

关于c++ - 在(任意大)流中搜索精确的字符串匹配 - C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57109823/