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

例如，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)); 
     } 
    }

但根据我的理解它去N^2，我们才能它更快我引用了前面的问题，并有链接后缀树http://allisons.org/ll/AlgDS/Tree/Suffix/，但它似乎并没有解决我的问题....输出，我从后缀树得到{1：abcd 2：bcd 3：cd 4：d} 任何人都可以帮我找出最快的方法来做到这一点吗？类似于线性时间？提前致谢.....

来源

2013-03-31 user2228588

你甚至不可能比O（n^2）更快地列出每个可能的子串的起始点和结束点，因为有O（n^2）个这样的子串！如果你想完整地打印出每个子字符串（就像你现在正在做的那样），那么时间复杂度就会上升到O（n^3），因为打印每个子字符串需要的时间与整个字符串长度成正比。 –

另请注意，空字符串也是有效的子字符串。 – Philip

如果你要对一组没有“触及”它们的子串进行查询，你只能使它更快。打印它们涉及所有这些。如果你想问一个问题，例如“什么是最长的子串出现至少两次”或者“哪个子串多于k个字符最频繁出现”，那么你可以在不枚举所有子串（带后缀树）的情况下这样做。 – harold

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

我不认为你的代码可以在任何重要的方式进行改进。

我应该注意到，优化这个代码是徒劳无益的做法，因为实际表现，都将通过写入字符输出流的开销支配......和任何操作系统与输出做流。

来源

2013-03-31 05:38:39

很好解释，希望逻辑被捕获在这里。 – kabuto178

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

回答

相关问题