Есть ли способ напечатать все подстроки строки в O (n) времени?

Question

У меня есть вход abcde. Я пытаюсь вывести что-то вроде этого:

a
ab
abc
abcd
abcde
b
bc
bcd
bcde
c
cd
cde
d
de
e

Я не могу сделать код без вложенных циклов. У меня вопрос, каково решение этой проблемы с O (n) сложностью времени?

Мой код указан ниже:

s = "abcde"  
for i in range(len(s)):
    for x in range(i, len(s) + 1):
        a = s[i:x]
        if a != "": print(a)

Answer 1

Позволяет делать это без вложенного l oop!
Это игра с библиотекой random, но время выполнения похоже на ваш код.

from random import randint
list1=[]
str1='abcde'
while len(list1)!=int(((len(str1)+1)*len(str1))//2):
    i=randint(0,len(str1))
    j=randint(0,len(str1))
    i,j=max(i,j),min(i,j)
    if i!=j:
        a=str1[j:i]
        if a not in list1:
            list1.append(a)
            print(a)

если строка, str1 = 'abcdef', он печатает:

de
abcdef
cdef
abc
ef
d
c
abcd
b
abcde
def
bcde
f
bcdef
a
bcd
cd
e
ab
cde
bc 

Теперь, если вы хотите, чтобы ваши данные в указанном вами порядке, используйте sort:

list1.sort()

Answer 2

Если вы также печатаете подстроки, временная сложность увеличивается до O(N^3), потому что каждая подстрока имеет длину O(N), поэтому вы будете печатать O(N^2) подстрок за O(N) время каждая для общей сложности. O(N^3). Смотрите дубликат Найдите все возможные подстроки самым быстрым способом .

В качестве примечания можно избежать проверки пустой строки, изменив внутреннюю l oop на начало i+1, что является (очень) небольшой оптимизацией.

s = "abcde"
for i in range(len(s)):
    for x in range(i+1, len(s)+1):
        a = s[i:x]
        print a