python - 查找长 Python 字符串的所有唯一子字符串 - 性能

Question

我以为我手头有一个非常简单的问题——找到给定字符串的所有子字符串。

我这样做如下：

unique_substrings = list(set([p[i:j+1+i] for i in range(len(p)) for j in range(len(p))]))

但是性能很差。在一个随机生成的长度为 900 的字符串上，我需要 1.5 秒。然后我对每个子字符串进行基于长度的数学运算，这进一步花费了更多时间，增加了 3-4 秒。

如何在时间方面提高性能？

这里已经有一个类似的答案，但它与记忆有关。内存不是我的瓶颈。

标签： pythonarraysstring

Answer 1

如果您考虑当前的起点和点在哪里，则可以将循环迭代次数减半。目前，i + j经常超过字符串的长度。

而是尝试：

substrings = {p[i:j] for i in range(len(p)) for j in range(i + 1, len(p) + 1)}

在这里，我们更改语义以创建i起点和j终点，强制执行j > i。

这将不包括空字符串""。substrings.add("")如果合适，添加它。