CODEWITHSUNDEEP
javastring
user2271868
user2271868

Reputation:

How to efficiently form array of suffixes?

I was looking for approach make array of suffixes at Java.
I found two ability variants. Moreover I want much more deeply understand differents between this variants.
Includes running time & space.

Code (suffixes):

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;
}

Code (StringBuilder suffixes):

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;
}

Question:

Upvotes: 4

Views: 234

Answers (5)

Damian Leszczyński - Vash
Damian Leszczyński - Vash

Reputation: 30875

At the end you always require n + 1 string to complete this task. Only thing that can be optimized is the time when those objects are created.

You could create the string representation as char array and lazy (on demand) return the suffixes.

You can use Iterable and Iterator interfaces to do that: 

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
        }

    }

}

You could implement the key functionality over a char array.

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() {

}

}

But IMHO is more complex and we do not gain nothing.

The advantage of this solution is that you can work on results and decide to stop before all prefixes are created.

Upvotes: 0

Ajinkya
Ajinkya

Reputation: 22720

The only difference between your code snippets is using String or StringBuilder, also you are using it only to retrieve sub string.
subString() from StringBuilder does

 new String(offset + beginIndex, endIndex - beginIndex, value);

and subString() from String does 

 new String(offset + beginIndex, endIndex - beginIndex, value);

both are same and creates new String so there wont be any difference in performance

Upvotes: 0

The Cat
The Cat

Reputation: 2475

You could do this, which avoids the substring method,

public String[] suffix(String s)
{
    String[] suffixes = new String[s.length()];
    String suffix = null;
    for (int i = 0 ; i < s.length() ; i++)
    {
        suffix = suffix == null ? "" + s.charAt(i) : suffix + s.charAt(i);
        suffixes[i] = suffix;
    }

    return suffixes;
}

not sure if it is any faster though.

Upvotes: 0

Danstahr
Danstahr

Reputation: 4319

The most efficient way would be to use a char array. However, it won't be so significant as the most costy operation is creating the String objects.

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);

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726919

There will be no discernable difference between the two ways of doing it that you describe: since Strings in Java are immutable, a new object will be created for each suffix. Making a substring from a String vs. StringBuilder will not give you much difference in performance, compared to allocations and copying required to set up the new string objects.

When you are looking for a suffix, passing the end index is not necessary: use the overload that takes a single int instead:

for (int i = 0; i < N; i++)
    suffixes[i] = s.substring(i);

Upvotes: 3

Related Questions