有没有一种方法可以在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)

- Azmain1234

---

如果 n 被认为是输入的长度，那是不可能的。 - user2390182

顺序重要吗？ - Mr.Dark

不，这没关系。 - Azmain1234

Answer 1

有没有一种方法可以在 O(N) 时间内打印出一个字符串的所有子字符串？

不，这是从数学上讲不可能的。

长度为 N 的字符串有 O(N^2) 个子字符串。你不能在 O(N) 的时间内打印出 O(N^2) 个字符串，即使这些字符串都是单独打印时间为O(1)。（它们不是。平均子字符串长度也是 N 的函数。）

即使使用并行技术，也无法实现 O(N)。如果（假设）有 P > N 的处理器来生成这些字符串，则对它们进行“打印”是一个无法并行化的过程。

补充说明，尽管可以编写避免显式嵌套循环的代码，但这并不改变比 O(N^3) 更好的解决方案在数学上不可能的事实。

- Stephen C

Answer 2

如果你也打印子字符串，时间复杂度将增加到O(N^3)，因为每个子字符串的长度都是O(N)，所以你将在O(N)的时间内打印O(N^2)个子字符串，总体复杂度为O(N^3)。请参见重复项以最快的方式查找所有可能的子字符串。

顺便说一下，你可以通过将内部循环更改为从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

- aeternalis1

---

这并不能解决 OP 的问题。他不需要嵌套循环。 - Mr.Dark

一个不需要嵌套循环的方案是可以实现的。 - Mr.Dark

这不是关于嵌套循环的问题，而是关于时间复杂度的问题。也许有一种不需要嵌套循环的解决方案，但在少于O(N^3)的时间内打印出O(N^3)个字符是不可能的。 - aeternalis1

这个回答不相关，这不是被问到的内容！ - Yudhishthir Singh

Answer 3

让我们不使用嵌套循环来完成这个任务吧！
这是一个使用了随机库的游戏，但执行时间与您的代码相似。

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()

- Joshua Varghese

---

这不是所要求的 O(N)。它是 O(N^3)。没有 O(N) 的解决方案。 - Stephen C

甚至还不起作用。 - Loren Pechtel