找到最快的方式所有可能的子字符串 [英] Find all possible substring in fastest way

问题描述

有关如字符串A =ABCD 那么答案应该是{A，AB，ABC，ABCD，B，BC，BCD，C，CD，D}（我不知道是否这一切都被称为子或没有，但我假设所以......）

For eg String A= "abcd" then answer should be {a,ab,abc,abcd,b,bc,bcd,c,cd,d} (I dont know whether this all are called substring or not but I am assuming so...)

要找到我已经使用下面的方法的所有子

To find all the substring I have used following method

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

但根据我的理解它去N ^ 2我们可以让它更快一点我refered透水问题，有链接后缀树的 http://allisons.org/ll/AlgDS/Tree/Suffix/ 但似乎犯规来解决我的问题....输出这是我从后缀树得到的是{1 ：A B C D  2：BCD  3：CD  4：D} 任何一个可以请帮我找最快的做到这一点的方法吗？类似的线性时间？在此先感谢.....

But according to my understanding it goes to N^2 can we make it faster I refered pervious question and there was link for suffix tree http://allisons.org/ll/AlgDS/Tree/Suffix/ but it doesnt seem to solve my problem.... output which i get from suffix tree is {1:abcd 2: bcd 3: cd 4: d} can any one please help me out to find fastest way to do this? something like in linear time ?Thanks in advance.....

推荐答案

您不能创建 O（N ^ 2）的字符串长度超过 O（N ^ 2）的时间。它是一个数学不可能的。即使创建一个字符串了一条指令，这仍然是一个 O（N ^ 2）的计算。

You can't create O(N^2) strings in better than O(N^2) time. It is a mathematical impossibility. Even if creating a string took one instruction, that is still a O(N^2) computation.

我不认为你的code可以在任何显著的方式来改善。

I don't think your code can be improved upon in any significant way.

我应该看到，这种优化code是徒劳的活动，因为实际的表现，都将被写入字符输出流的管理费用为主......和任何操作系统不与输出流

I should observe that optimizing this code is a futile activity, since the actual performance is going to be dominated by the overheads of writing the characters to the output stream ... and whatever the OS does with the output stream.

这篇关于找到最快的方式所有可能的子字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！