Поиск всех уникальных подстрок длинной строки 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 секунды.

Как я могу улучшить производительность с точки зрения времени?

Уже естьаналогичный ответ здесь , но он относится к памяти.Память не мое узкое место.

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(""), если необходимо.