python - 如何比较字典中的键并查看一个键是否包含另一个键？

Question

这里是一个词作为键的字典，

count_dict = {
    'apple':2,
    'pie': 1,
    'pi':1,
    'applepie':1
}

如果一个长词包含另一个短词，则将长词的计数加到短词上。这意味着结果是:

{
  'apple':3,
  'pie': 2,
  'pi':3,
  'applepie':1
}

最简单的方法是使用一个简单的循环，

for i in list:
    for j in list:
        if len(i) < len(j) and i in j:
            count_dict[i] += 1

但是时间复杂度是O(n^2)，太费时间了。有什么办法可以降低复杂度来解决这个问题？

Answer 1

是的，您可以使用 Suffix tree 在 O(n) 时间内完成, 特别是看到 generalized suffix tree .您首先创建所有键的后缀树，之后您可以迭代每个键并在后缀树中搜索每个键(花费 O(len(key)) 时间)。

在你的树中找到 key 后，你可以找到你的 key 的所有子树，这些子树正是包含你的 key 的较长 key ，因此你可以获取每个子树并更新你的字典。

如果 m 是常量(比如你的键最多 100 个字符长)那么子树的数量也将是常量(最多一个高度为 100 的子树)所以整个事情花费 O(n) 时间。

---

您可以使用 suffix array 而不是后缀树这是此类数据结构的更节省空间的版本。