c++ - 是否有一些快速算法可以检查两个字符串集中的子字符串

Question

有两个字符串集(C++)

set<string> set1, set2;

我需要迭代set1以检查set1中的任何字符串是否为set2中字符串的子字符串。
下面的代码是我的解决方案，有没有快速的算法？

for(auto& str1 : set1) {
    for(auto& str2: set2) {
        if (strstr(str2.data(), str1.data()))
           // do something
    }
}

有一些限制

此功能用于在线RPC服务器

set2和set1的

候选对象可能太大而无法完全加载到内存中，因此我无法建立一些索引，例如trie或缓存结果。

Answer 1

后缀树会更快一些，O(n + m) 其中n是set1中所有字符串的总长度，set2中m的总长度，在最坏的情况下，您的设置方法将是O(n*m*min(n,m))，后缀数组也使用线性内存。
如果它不适合RAM，则可以考虑将其拆分为适合的“块”，然后针对set2检查set1中所有对的“块”，并在它们上构建后缀树。
另外，如果硬件具有SSD，则虚拟内存现在也非常快