以最快的方式查找所有可能的子串

Question

对于字符串A ="abcd",则答案应为{a,ab,abc,abcd,b,bc,bcd,c,cd,d}

要查找我使用以下方法的所有子字符串

{a,ab,abc,abcd,b,bc,bcd,c,cd,d} 

但根据我的理解,复杂性是O(N ^ 2).我们可以加快速度吗？我提到了以前的问题,后缀树http://allisons.org/ll/AlgDS/Tree/Suffix/有链接,但它似乎没有解决我的问题....我从后缀树得到的输出是{1: abcd 2:bcd 3:cd 4:d}任何人都可以帮我找出最快的方法吗？像线性时间的东西？

Answer 1

您不能O(N^2)在更好的O(N^2)时间内创建字符串.这是一种数学上的不可能性.即使创建一个字符串只需要一条指令,这仍然是一个O(N^2)计算.

抛开复杂性,我认为您的代码无法以任何重要方式得到改进.

我应该观察到优化这段代码是徒劳的,因为实际的性能将由将字符写入输出流的开销以及操作系统对输出流所做的任何事情来控制.