6

現在、2 つのネストされた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)。私のコードを見ると、すべての部分文字列をリストに追加しているので、誰でも不可能だと示唆することができます。しかし、私の目的はすべての部分文字列を保存することではなく、辞書編集的に i 番目に小さい文字列を見つけることです。

4

1 に答える 1

14

さまざまな 部分文字列があるため、 !O(n^2)よりも優れた複雑さでそれらすべてを列挙できるアルゴリズムはありません。O(n^2)

ただし、辞書編集的に最小の部分文字列を見つける問題は、まったく別の問題です。それは常に空の文字列なので、これはO(1)操作です (そして非常に無意味なものでもあります)。

于 2012-04-11T12:47:30.470 に答える