有没有办法在 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

如果您还打印子字符串，时间复杂度会上升到 O(N^3)，因为每个子字符串的长度为 O(N)，因此您将打印 O(N^2) 个子字符串 O(N) 次，总复杂度为 O(N^3)。请参阅副本 Find all possible substring in fastest way。

附带说明一下，您可以通过将内部循环更改为从 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

Answer 2

让我们在没有嵌套循环的情况下做到这一点！
这是一个带有 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 3

Is there a way to print all substrings of a string in O(N) time?

不，没有。这在数学上是不可能的。

长度为 N 的字符串有 O(N^2) 个子字符串。您无法在 O(N) 时间内打印 O(N^2) 个字符串。即使字符串全部（单独） O(1) 打印也不行。（它们不是。平均子串长度也是 N 的函数。）

即使是并行性也不会让您达到 O(N)。如果（假设）有一个 P > N 处理器来生成字符串，打印它们是一个无法并行化的过程。

郑重声明，可以通过避免显式嵌套循环的方式对其进行编码。但这并没有改变比 O(N^3).

更好的解决方案的基本数学不可能性

有没有办法在 O(n) 时间内打印字符串的所有子字符串？

Is there a way to print all substrings of a string in O(n) time?

python

string

time-complexity

nested-loops