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

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（密钥））时间）。

在树中找到密钥后，您可以找到密钥的所有子树，这些密钥恰好是包含密钥的较长密钥，因此您可以更换每个密钥并更新您的密码。

如果m是常数（假设你的键长度最多为100个字符）那么子树的数量也将是常数（最多为高度为100的子树），因此整个过程需要O（n）时间。

---

您可以使用suffix array而不是后缀树，而

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

keys = list(count_dict.keys())
res_dict = {}
for i, k1 in enumerate(keys):
    res_dict[k1] = res_dict.setdefault(k1, count_dict[k1])
    for k2 in keys[i+1:]:
        if k1 in k2:
            res_dict[k1] += count_dict[k2]
        elif k2 in k1:
            res_dict[k2] = res_dict.setdefault(k2, count_dict[k2]) + count_dict[k1]
        else:
            continue
print(res_dict)  # -> {'apple': 3, 'pie': 2, 'pi': 3, 'applepie': 1}

是此类数据结构的更节省空间的版本。

Answer 2

这可能比O（n ^ 2）好一些，但是大O符号不是我的强项。看一看：

qazxswpoi