时间戳

首页 > 解决方案 > 是否有一些快速算法来检查两个字符串集中的子字符串

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

问题描述

有两个字符串集（c++）

set<string> set1, set2;

我需要迭代 set1 以检查 set1 中的任何字符串是否是 set2 中字符串的子字符串。

下面的代码是我的解决方案，有什么快速算法吗？

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

有一些限制

  1. 此功能用于在线 RPC 服务器
  2. set2 和 set1 的候选对象可能太大而无法完全加载到内存中，因此我无法构建诸如 trie 或缓存结果之类的索引。

标签： c++stringalgorithm

解决方案

后缀树会更快，O(n + m) 其中nset1 和 set2 中所有字符串的总长度在哪里m，您的 set 方法O(n*m*min(n,m))在最坏的情况下，后缀数组也使用线性内存。

如果它不适合 RAM，您可以考虑将其拆分为适合的“块”，然后检查来自 set1 和 set2 的所有“块”对并在它们上构建后缀树。

另外，如果硬件有SSD，现在虚拟内存也很快

推荐阅读