我可以生成复杂度为<O（n^2）的所有子字符串

目前我使用两个嵌套for循环来生成字符串的所有子字符串。我听说Suffix Tree，但AFAIK Suffix Tree生成后缀不是子字符串。以下是目前我正在using-我可以生成复杂度为<O（n^2）的所有子字符串

 String s = "abacbccca"; 
     int l = s.length(); 
     for (short c = 0; c < l; c++) { 
      for (short r = 0; r < l - c; r++){ 
       Sting ss=s.substring(c, c + r + 1);           
       if(!t.contains(ss)); 
        t.add(ss); 
      } 
     }

的代码，我想一个办法，可以产生在不到O(n^2)所有子。尽管通过查看我的代码，任何人都可以建议我这是不可能的，因为我将每个子字符串添加到列表中。但我的目标不是存储所有的子字符串，我的目标是找到一个按字典顺序排列成最小字符串的字符串。

来源

2012-04-11 Ravi Joshi

如果您只对字典上最小的字符串感兴趣，那么恐怕Niklas B.下面是正确的。但是如果你对O（n）大小的数据结构感兴趣，它允许你访问任何给定i的第i个最小字符串，正如你的问题似乎表明的那样，那么也许我对[这个问题]的答案（http： //stackoverflow.com/q/9389681/777186）帮助。 – jogojapan 2012-04-11 13:55:55

@jogojapan：是的....那就是我想要的......非常感谢你...... – 2012-04-11 14:28:20

有是O(n^2)不同的子串，所以没有一个算法可以列举所有的复杂性好于O(n^2)！

虽然找到字典顺序最小的子字符串的问题是完全不同的。它总是空的字符串，所以这是一个O(1)操作（也是一个非常无意义的操作）。

来源

2012-04-11 12:47:30

好的....你能否详细说说找到'字典中最小的子字符串？ – 2012-04-11 13:14:14

@Ravi：通常，当按字典顺序比较字符串时，[如果其中一个字符串是另一个字符串的前缀，则认为它较小]（http://en.wikipedia.org/wiki/Lexicographical_order#Ordering_of_sequences_of_various_lengths）。所以最小的子字符串总是空字符串：'String smallestSubstring（String x）{return“”; “顺便说一下，我也在我的回答中写了这个。 – 2012-04-11 13:20:37

如果不允许'null'，那么??? ..假设我们有字符串abacba，它有这些独特的子字符串{a，ab，aba，abac，abacb，abacba，b，ba，bac，bacb，bacba，ac，acb，acba，c，cb，cba} '。现在按字母顺序排列的最小字符串是上面的集合'a'。 – 2012-04-11 13:23:00

我可以生成复杂度为<O（n^2）的所有子字符串

回答

相关问题