python - 删除列表中的子字符串，复杂度优于 O(n^2)

Question

我有一个包含很多单词(100.000+)的列表，我想做的是删除列表中每个单词的所有子字符串。

为简单起见，假设我有以下列表:

words = ['Hello', 'Hell', 'Apple', 'Banana', 'Ban', 'Peter', 'P', 'e']

所需的输出如下:

['Hello', 'Apple', 'Banana', 'Peter']

• 'Hell' 已被删除，因为它是 'Hello'
的子字符串
• 'Ban' 已被删除，因为它是 'Banana'
的子字符串
• 'P' 已被删除，因为它是 'Peter'
的子字符串
• 'e' 已被删除，因为它是 'Hello'、'Hell' 的子字符串，'苹果'，等等。

我做了什么

这是我的代码，但我想知道是否有比这些嵌套理解更有效的方法。

to_remove = [x for x in words for y in words if x != y and x in y]
output = [x for x in words if x not in to_remove]

如何提高性能？我应该改用 regex 吗？

Answer 1

@wim 是正确的。

给定一个固定长度的字母表，以下算法在文本的总长度上是线性的。如果字母表的大小没有限制，那么它将是 O(n log(n))。无论哪种方式，它都比 O(n^2) 好。

Create an empty suffix tree T.
Create an empty list filtered_words
For word in words:
    if word not in T:
        Build suffix tree S for word (using Ukkonen's algorithm)
        Merge S into T
        append word to filtered_words