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

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

因此，为了简单起见，我们假设我有以下列表：

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

以下输出是所需的：

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

• 'Hell'被删除，因为它是一个子串'Hello'
• 'Ban'被删除，因为它是一个子串'Banana'
• 'P'被删除，因为它是一个子串'Peter'
• 'e'被删除，因为它是一个子串'Hello', 'Hell', 'Apple'， 等等。

我做了什么

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

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反而？

@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