筛选字符串列表，忽略其他项的子字符串

Question

我如何过滤包含字符串和子字符串的列表以只返回最长的字符串。（如果列表中的任何项是另一项的子字符串，则只返回较长的字符串。）

我有这个功能。有没有更快的方法？在

def filterSublist(lst):
    uniq = lst
    for elem in lst:
        uniq = [x for x in uniq if (x == elem) or (x not in elem)]
    return uniq

lst = ["a", "abc", "b", "d", "xy", "xyz"]
print filterSublist(lst)

> ['abc', 'd', 'xyz']
> Function time: 0.000011

Answer 1

简单的二次时间解决方案如下：

res = []
n = len(lst)
for i in xrange(n):
    if not any(i != j and lst[i] in lst[j] for j in xrange(n)):
        res.append(lst[i])

但我们可以做得更好：

让$是一个不出现在任何字符串中的字符，其值比所有实际字符的值都要低。在

让S是所有字符串的串联，中间是$。在您的示例中，S = a$abc$b$d$xy$xyz。在

您可以在线性时间内生成S的suffix array。您还可以使用我描述的一个更简单的O（nlog^2n）构造算法in another answer。在

现在，对于lst中的每个字符串，检查它是否只在后缀数组中出现一次。可以进行两次二进制搜索来查找子字符串的位置，它们在后缀数组中形成一个连续的范围。如果字符串出现多次，则将其删除。在

通过预先计算LCP信息，这也可以在线性时间内完成。在

示例O（n log^2 n）实现，改编自my suffix array answer：

^{pr2}$

然而，解释开销很可能导致这比O（n2）方法慢，除非S真的很大（大约10^5个字符或更多）。在