我可以生成复杂度<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)操作(也是一个非常无意义的操作).