4

Javaでサフィックスの配列を作成するアプローチを探していました。
2 つの能力のバリエーションを見つけました。さらに、このバリアント間の相違点をより深く理解したいと思っています。&
が含まれます 。 running timespace

コード (サフィックス):

public static String[] suffixes(String s)
{
int N = s.length();
String[] suffixes = new String[N];
for (int i = 0; i < N; i++)
suffixes[i] = s.substring(i, N);
return suffixes;
}

コード (StringBuilder サフィックス):

public static String[] suffixes(String s)
{
int N = s.length();
StringBuilder sb = new StringBuilder(s);
String[] suffixes = new String[N];
for (int i = 0; i < N; i++)
suffixes[i] = sb.substring(i, N);
return suffixes;
}

質問:

  • 接尾辞の配列を効率的に形成するには?
4

5 に答える 5

0

最後に、このタスクを完了するには常に n + 1 文字列が必要です。最適化できるのは、それらのオブジェクトが作成される時間だけです。

文字列表現を char 配列として作成し、lazy (オンデマンド) でサフィックスを返すことができます。

これを行うには、 Iterable および Iterator インターフェースを使用できます。

public class StringSufixies implements Iterable<String> {

    private final String input; 

    public StringSufixies(String input) {
        this.input = input;
    }

    @Override
    public Iterator<String> iterator() {
        return new SuffixStringIterator(input);
    }

    private static class SuffixStringIterator implements Iterator<String> {

        private final String input;
        private final int size;
        private int suffixId;

        private SuffixStringIterator(String input) {
            this.input = input;
            this.size  = input.length();
            this.suffixId = 1;
        }

        @Override
        public boolean hasNext() {
            return suffixId <= size;
        }

        @Override
        public String next() {
            return input.substring(0, suffixId++); //At this point we create new String
        }

        @Override
        public void remove() {
            //Add throw or other impl
        }

    }

}

主要な機能を char 配列に実装できます。

private static class SuffixCharIterator implements Iterator<String> {

private final char[] charSequence;
private final int size;
private int suffixId = 0;

private SuffixCharIterator(char[] charSequence) {
    this.charSequence = charSequence;
    this.size = charSequence.length;
}

@Override
public boolean hasNext() {
    return suffixId <= size;
}

@Override
public String next() {
    return new String(charSequence, 0, suffixId++); //At this point we create a new String
}

@Override
public void remove() {

}

}

しかし、私見はもっと複雑で、何も得られません。

このソリューションの利点は、結果に取り組み、すべてのプレフィックスが作成される前に停止することを決定できることです。

于 2013-04-16T12:27:05.070 に答える
0

最も効率的な方法は、char 配列を使用することです。ただし、最もコストのかかる操作は String オブジェクトの作成であるため、それほど重要ではありません。

String s = "foobarbaz"; 
char[] cha = s.toCharArray();
int length = cha.length;
String[] suffixes = new String[length];
for (int i = 0; i < length; ++i)
  suffixes[i] = new String(cha, i, length-i);
于 2013-04-16T11:37:39.277 に答える