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

substring performance algorithm time-complexity java

2022-09-01 01:32:09

对于字符串 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
}

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

答案 1

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

撇开复杂性不谈，我不认为你的代码可以以任何重要的方式进行改进。

我们能让它更快吗？

可能不是。

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

答案 2