Python 中的字符串匹配

我在列表中存储了300K个字符串，每个字符串的长度在10到400之间。我想删除那些作为其他字符串的子字符串的字符串（长度较短的字符串有更高的概率是其他字符串的子字符串）。

目前，我首先根据长度对这 300K 字符串进行排序，然后使用以下方法。

sorted_string = sorted(string_list, key=length, reverse=True)
for item in sorted_string
    for next_item in sorted_string[sorted_string.index(item)+1:]
        if next_item in item:
            del sorted_string[sorted_string.index(next_item)]

该方法的运行时间为O(n^2)。由于我有300K字符串，所以我对这种方法不满意。

我尝试将这些排序的字符串分成不同的块，并使用多重处理来计算每个块。我的第一个想法是将前 10K 放入第一个块，接下来的 10K 放入第二个块，依此类推。但这样，每个块中的字符串具有相似的长度，并且它们可能不会成为同一块中其他字符串的子串。所以这不是一个好的划分策略。

有什么好主意吗？

Edit：这些字符串代表 DNA 序列，并且仅包含 'g'、'c'、't' 和 'a'

Update:

我尝试使用以下代码构建后缀树https://github.com/kvh/Python-Suffix-Tree。该程序基于以下内容构建后缀树乌科宁算法.

连接字符串的总长度约为90,000,000。这是一个很大的数字。该程序已运行半小时，仅处理了约 3,000,000 (1/30) 个字符。我对这个计划并不满意。

有没有其他后缀树构建算法可以处理这么大的字符串？

你可以使用后缀树。它会让你得到 O(mn)，其中 m 是字符串的长度。它仍然是二次的，但由于在您的情况下 m

这些讲义提供了一个很好的直观解释，说明如何使用后缀树来查找子字符串。