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

Question

目前我正在使用两个嵌套的for 循环来生成字符串的所有子字符串。我听说过 Suffix Tree 但 AFAIK Suffix 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) 操作(也是一个非常没有意义的操作)。