Как сравнить ключи в словаре и посмотреть, содержит ли один ключ другой?

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

Это, вероятно, немного лучше, чем O (n ^ 2), но большие обозначения O не моя сильная сторона. Посмотрите:

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) время, используя Дерево суффиксов , в частности, см. Обобщенное дерево суффиксов . Сначала вы создаете суффиксное дерево для всех ключей, после чего вы можете выполнять итерацию по каждому ключу и для каждого искать его в суффиксном дереве (занимает время O (len (key))).

После того, как вы нашли ключ в своем дереве, вы можете найти все поддеревья вашего ключа, и именно эти ключи являются именно более длинными ключами, в которых содержится ваш ключ, поэтому вы можете взять каждый из них и обновить свой диктант.

Если m является константой (скажем, ваши ключи длиной не более 100 символов), тогда число поддеревьев также будет постоянным (не более поддерева высоты 100), и поэтому все это занимает O (n) время.

---

Вместо дерева суффиксов вы можете использовать массив суффиксов , который является более компактной версией этого типа структуры данных.