是否存在O(n)时间复杂度的高效列表子串过滤算法？

你当前的双层循环逻辑能得到正确结果，但时间复杂度是O(n²*L)（n是列表元素个数，L是字符串平均长度），列表规模稍大时性能会很差，下面给两个不同场景下的更优实现：

剪枝优化版双层循环（中小数据量首选，改造成本极低） #

核心优化点：已经被标记为要移除的字符串，本身就不会出现在最终结果里，不需要再拿它当母串去匹配更短的字符串，直接跳过这类无效循环即可。

items = ['df', 'gb', 'd', 'abc', 'def', 'ab',  'f', 'g']
# 按字符串长度降序排序
items_sorted = sorted(items, key=len, reverse=True)
to_remove = set()

for i in range(len(items_sorted)):
    current_long = items_sorted[i]
    # 已经标记为待删除的串，直接跳过不做母串
    if current_long in to_remove:
        continue
    for j in range(i + 1, len(items_sorted)):
        current_short = items_sorted[j]
        if current_short in current_long:
            to_remove.add(current_short)

new_items = [s for s in items_sorted if s not in to_remove]
print(new_items)
# 输出元素和预期完全一致：['def', 'abc', 'df', 'gb']，仅排序顺序有差异，如需固定顺序可在最后一步按需调整排序规则即可

这个版本比你原来的写法少了大量无意义的匹配，在列表元素为几百上千条的场景下性能足够，代码也容易维护。

AC自动机线性复杂度实现（超大规模数据适用） #

如果你的列表有上万甚至更多字符串，双层循环的O(n²)复杂度会成为明显瓶颈，这时候可以用Aho-Corasick多模式匹配算法把时间复杂度降到接近线性：

1. 先把所有字符串按长度分组
2. 从最短的字符串开始构建AC自动机的模式集
3. 遍历所有比当前模式长的字符串，一次性匹配出所有包含的子串，标记为待移除

这种方案不需要两两比较字符串，所有字符串只需要遍历常数次，数据量越大性能优势越明显。日常开发如果不想手动实现AC自动机，也可以直接用成熟的多模式匹配第三方库快速接入。

内容的提问来源于stack exchange，提问作者marlon