java - 我可以生成复杂度 < O(n^2) 的所有子字符串吗

Question

目前我正在使用两个嵌套for循环来生成字符串的所有子字符串。我听说过，Suffix Tree但 AFAIKSuffix Tree生成后缀而不是子字符串。以下是我目前正在使用的代码 -

        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)。尽管通过查看我的代码，任何人都可以建议我这是不可能的，因为我正在将每个子字符串添加到列表中。但我的目标不是存储所有子字符串，我的目标是找到一个在字典上是最小字符串的字符串。

Answer 1

有不同的 O(n^2)子串，所以没有算法能以比O(n^2)!

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