Geek Answers Handbook

How to effectively form an array of suffixes?

I was looking for an approach to make an array of suffixes in Java.
I found two options for ability. Moreover, I want to better understand the differences between these options.
Includes running time and 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:

  • How to effectively form an array of suffixes?
+4
source share
5 answers

There will be no distinguishable difference between the two methods of its execution: since String in Java is immutable, a new object will be created for each suffix. Creating a substring from String vs. StringBuilder will not give you a big difference in performance compared to the distributions and copying necessary to configure new string objects.

When you are looking for a suffix, passing the final index is not required: use an overload that takes only one int :

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

The only difference between your code snippets is the use of String or StringBuilder, also you use it only to get a substring.
subString() of StringBuilder does

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

and subString() of String does

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

both are the same and create a new line, so there will be no difference in performance

0
source

The most efficient way is to use a char array. However, it will not be as significant as the most expensive operation to create 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);
0
source

You can do this, avoiding 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 he is faster.

0
source

In the end, you always need the string n + 1 to complete this task. The only thing that can be optimized is the time it takes to create these objects.

You can create a string representation as a char array and lazy (on demand) returning suffixes.

You can use Iterable and Iterator interfaces for this:

 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 can implement 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 complicated, and we get nothing.

The advantage of this solution is that you can work on the results and make a decision to terminate before creating all the prefixes.

0
source

More articles:


All Articles