Код, который вы привели,

def uniq_subs$s$:
res = set for i in range$len(s)$:
for j in range$i+1,len(s)+1$:
res.add$s[i:j]$ return res

корректен, но очень неэффективен. Разберём почему и какие есть более быстрые подходы, с оценкой сложности и примерами реализации на Python.

1) Оценка сложности исходного кода

Количество порождаемых подстрок = n$n+1$/2 = Θ$n^2$.Каждое s$$i:j$$ — срез строки, который копирует $j-i$ символов. Суммарный объём копируемых символов = Θ$n^3$ $точноn(n+1)(n+2)/6$.Хеширование/вставка строки в set также занимает O$length$ для каждой строки.
Итого: время Θ$n^3$ в худшем случае; память — хранение всех уникальных подстрок занимает Θ$n^2$ строк и Θ$n^2$ символов в сумме.

Для даже умеренно больших n $напримерn=10^4$ это невозможно.

2) Цель: посчитать количество различных подстрок $илипростополучитьмножествоуникальных$ — алгоритмы лучше O$n^2$ по времени и O$n$ по памяти существуют.

Основные эффективные подходы

Суффиксный массив + LCP: построить суффиксный массив SA $времяO(nlogn)впростыхреализациях;существуютO(n)алгоритмы$, затем LCP $Кэсай$ за O$n$. Количество уникальных подстрок = n*$n+1$/2 − sum$LCP$.

Сложность: O$nlogn$ $впростомвариантессортировкой$ или O$n$. Память: O$n$.Подходит, если нужно только количество, и если реализовать SA аккуратно $вPythonSAO(nlogn)обычноприемлем$.

Суффиксный автомат $SuffixAutomaton,SAM$: строится за O$n$ и позволяет посчитать число различных подстрок как сумма по вершинам: sum$len[v]-len[link[v]]$.

Сложность: O$n$ время, O$n$ память $числосостояний\le 2n-1$. В Python реализуется компактно.Очень удобен для подсчёта, поиска k‑й лексикографической подстроки и т. п.

Суффиксное дерево $Ukkonen$: O$n$ время, O$n$ память, но сложнее в реализации на Python.

Хеши $rollinghash$: можно посчитать хеши всех подстрок фиксированной длины L за O$n$ и получить число различных подстрок длины L. Но суммирование по всем L даёт O$n^2$ время. Можно комбинировать с бинпоиском — но для общего подсчёта уникальных подстрок всё равно менее эффективно, чем SAM/SA.

3) Рекомендации

Если нужно только количество различных подстрок — используйте SAM или SA+LCP.Если нужно сам набор всех уникальных подстрок $перечислить$, то размер результата может быть Θ$n^2$ и это физически дорого; в этом случае подумайте, действительно ли нужно перечисление, или достаточно статистики/ограничения по длине.В Python обычно проще и быстрее писать SAM для задач подсчёта; SA с сортировкой $doubling+tuplesort$ тоже часто хорош и понятен.

4) Код: суффиксный автомат $быстрыйикомпактный$. Возвращает количество различных подстрок.

def count_distinct_substrings_sam$s$:

Возвращает количество различных подстрок строки ssa_trans = # список словарей переходов
sa_link = sa_len =
sa_trans.append{} # state 0
sa_link.append$-1$ sa_len.append$0$ last = 0
for ch in s:
cur = len$s{a}_{t}rans$ sa_trans.append{} sa_len.append$s{a}_{l}en[last]+1$ sa_link.append$0$
p = last
while p != -1 and ch not in sa_trans$$p$$:
sa_trans$$p$$$$ch$$ = cur
p = sa_link$$p$$ if p == -1:
sa_link$$cur$$ = 0
else:
q = sa_trans$$p$$$$ch$$ if sa_len$$p$$ + 1 == sa_len$$q$$:
sa_link$$cur$$ = q
else:
# clone q
clone = len$s{a}_{t}rans$ sa_trans.append$s{a}_{t}rans[q].copy()$ sa_len.append$s{a}_{l}en[p]+1$ sa_link.append$s{a}_{l}ink[q]$ while p != -1 and sa_trans$$p$$.get$ch$ == q:
sa_trans$$p$$$$ch$$ = clone
p = sa_link$$p$$ sa_link$$q$$ = sa_link$$cur$$ = clone
last = cur
# число различных подстрок = сумма $len[v]-len[link[v]]$ по всем состояниям v>0
res = 0
for v in range$1,len(s{a}_{t}rans)$:
res += sa_len$$v$$ - sa_len$$s{a}_{l}ink[v]$$ return res

Сложность: O$n$ в среднем и худшем для реализаций SAM; память O$n$ состояний $каждое—dictпереходов,попамятинемного«дороже»чеммассивы,новсёжелинейно$.

5) Код: суффиксный массив + LCP $простаяреализацияO(nlogn)из-засортировки$

def count_distinct_substrings_sa$s$:
n = len$s$

постройка SA методом "doubling"sa = list$range(n)$ rank_ = $$ord(c)forcins$$ + $$-1$$ k = 1
while k <= n:
sa.sort(key=lambda i: (rank_[i], rank_[i + k] if i + k < n else -1))
tmp = $$0$$ * n
for i in range$1,n$:
prev, cur = sa$$i-1$$, sa$$i$$ tmp$$cur$$ = tmp$$prev$$ + ( (rank_[prev], rank_[prev+k] if prev+k<n else -1) != (rank_[cur], rank_[cur+k] if cur+k<n else -1) )
rank_$$:n$$ = tmp
k <<= 1
# Kasai LCP
rank_sa = $$0$$*n
for i, p in enumerate$sa$:
rank_sa$$p$$ = i
lcp = $$0$$*$n-1$ h = 0
for i in range$n$:
r = rank_sa$$i$$ if r == 0:
continue
j = sa$$r-1$$ while i+h < n and j+h < n and s$$i+h$$ == s$$j+h$$:
h += 1
lcp$$r-1$$ = h
if h:
h -= 1
total = n*$n+1$//2 - sum$lcp$ return total

Сложность: O$nlogn$ из-за сортировки с ключем; LCP — O$n$. Память O$n$.

6) Компромиссы памяти/времени

Naive $срезы+set$: очень дорого по времени $\Theta (n^3)$ и памяти $\Theta (n^2)$, но очень прост и достаточен для маленьких строк (n < ~500).Rolling hash: можно хранить только хеши $целыечисла$ вместо строк, что экономит память по сравнению со строками, но вычислительно всё ещё Θ$n^2$ по времени, и нужны меры против коллизий $двойнойхеш$.SAM: лучшее сочетание — линейное время и линейная память, но реализация на Python использует словари для переходов — это добавляет константные факторы по памяти/времени.SA+LCP: чуть более простая структура по памяти $массивы/списки$, быстрее в Python для некоторых входов $используетсортировкусбыстрымиC‑реализациями$, но асимптотика O$nlogn$ в простых реализациях.

7) Практические советы по Python

Если n ≤ ~2000, исходный подход можно использовать $нолучшезаменитьстрокинапредставленияввидесрезовпамяти—вPythonэтонереализуемовстроенно$.Для n ~ 10^4–10^6 используйте SAM или хорошо оптимизированный SA $иливызывайтеC/C++реализацию$.Если готовы потреблять больше памяти, храните в set не строки, а 64‑бит хеши $двойноймодульныйхеш$, но помните о рисках коллизий.

8) Резюме

Исходный алгоритм: Θ$n^3$ время, Θ$n^2$ память — неприемлем для больших n.Лучший выбор для подсчёта количества различных подстрок: суффиксный автомат $O(n)время/память$ или суффиксный массив + LCP $O(nlogn)простаяреализация$.Для перечисления всех уникальных подстрок размер вывода сам по себе может быть Θ$n^2$ — это ограничивает возможную оптимизацию.

Если нужно, могу:

Прислать готовую и оптимизированную реализацию SAM/SA+LCP, тесты и бенчмарки на ваших входных данных.Написать вариант, который возвращает само множество уникальных подстрок $спредупредениемобобъёмерезультата$ или вариант с хранением только хешей.