Python: удаление более длинных подстрок строки в наборе

Question

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

string = 'ABAAABAAB'
setA = {'ABAAAB', 'BAAAB', 'AAAB', 'AAB'}
setB = setA.copy()
setC = setA.copy()
for s1 in setA:
    len1 = len(s1)
    for s2 in setB:
        len2 = len(s2)
        if s1 in s2 and len2 > len1:
            setC.discard(s2)

Я создаю копию моего исходного набора и перебираю элементы setA, а затем setB.Если один из этих элементов является подстрокой другого элемента, я отбрасываю более длинный элемент.Время выполнения моего решения значительно увеличивается по мере увеличения элементов setA из-за использования вложенных циклов.Есть ли решение с меньшей временной сложностью?

Answer 1

Чтобы сделать алгоритм поиска подстроки @blhsing опубликованным немного проще для чтения, вы можете просто разделить шаги на их собственные циклы.Это та же логика, но не внутри одной строки.

setC = set()
sortedList = sorted(setA, key=len)
for substring in sortedList:
    if not substring_in_set(substring, set3):
        setC.add(substring)


# Checks whether the subtrings is in the set 
# and returns True or False
def substring_in_set(substring, set):
    for i in range(len(substring)):
        for n in range(len(substring) - i):
            if substring[i: i + n + 1] in set:
                return True
    return False

Answer 2

Вы можете перебирать setA от самой короткой строки до самой длинной и добавлять данную строку к setC, только если ни одна из возможных подстрок строки уже находится в setC.Вы можете сгенерировать все возможные подстроки из строки, перебирая начальный индекс по длине строки и перебирая размер подстроки от 1 до оставшейся длины строки из текущего начального индекса, а затем используя начальный индекс идлина подстроки для среза строки:

setC = set()
for s in sorted(setA, key=len):
    if not any(s[i: i + n + 1] in setC for i in range(len(s)) for n in range(len(s) - i)):
        setC.add(s)

setC становится:

{'AAB'}

Это улучшает общую сложность времени с O (n ^ 2) вашего решения для O (n log n) .