Python：删除s中字符串的较长子字符串

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

您可以在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 logn）。你知道吗

Answer 2

为了使子串搜索算法@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