41

对于 String A = "abcd" 那么答案应该是

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

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

for (int i = 0; i < A.length(); i++) {
    for (int j = i+1; j <= A.length(); j++) {
        System.out.println(A.substring(i,j));
    }
}

但根据我的理解，复杂性达到O(N^2). 我们可以让它更快吗？我提到了上一个问题，并且有后缀树的链接，但它似乎并没有解决我的问题。我从后缀树得到的输出是

{
 1: abcd
 2: bcd
 3: cd
 4: d
}

任何人都可以帮我找到最快的方法吗？像线性时间的东西？

4

1 回答 1

57

你不能O(N^2)比O(N^2)时间更好地创建字符串。这是数学上的不可能。即使创建一个字符串需要一条指令，那仍然是一个O(N^2)计算。

抛开复杂性不谈，我认为您的代码无法以任何重要的方式改进。

我们可以让它更快吗？

可能不是。

优化这段特定的代码是徒劳的。由于您正在将字符串写入标准输出，因此实际性能将取决于写入字符的开销......以及操作系统对输出所做的任何事情。

于 2013-03-31T05:38:39.740 回答