python - Python中的字符串匹配

Question

我在列表中存储了300K个字符串，每个字符串的长度在10到400之间。我想删除那些是其他字符串的子串的字符串(长度较短的字符串更有可能是子串其他的)。

目前我是先把这30万个字符串按长度排序，然后用下面的方法。

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 个字符串，我对这种方法并不满意。

我试图将这些排序后的字符串分成不同的 block ，并使用多处理来计算每个 block 。我的第一个想法是将第一个 10K 放入第一个 block ，然后将下一个 10K 放入第二个 block ，依此类推。但是这样一来，每个 block 中的字符串的长度都差不多，并且它们可能不是同一 block 中其他字符串的子字符串。所以这不是一个好的划分策略。

有什么好主意吗？

编辑:这些字符串代表DNA序列，只包含'g'、'c'、't'和'a'

更新:

我尝试使用 https://github.com/kvh/Python-Suffix-Tree 中的代码构建后缀树.该程序基于 Ukkonen's algorithm 构建后缀树.

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

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

Answer 1

你可以使用 suffix tree .它会让你达到 O(mn)，其中 m 是字符串的长度。它仍然是二次方的，但由于 m << n 在您的情况下，它会提供显着的改进。

These lecture notes提供了关于如何使用后缀树查找子字符串的非常直观的解释。