CODEWITHSUNDEEP
javaalgorithmsuffix-array
rents
rents

Reputation: 848

How to build a suffix array in Java 7+ in linear space?

In Pre-java 7, I could simply do the following:

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

However, in Java 7, the substring method returns a new string. So the space consumed will be O(n^2) where n is the length of the string.

Any quick and easy way to do the same in Java 7 and higher versions?

Upvotes: 1

Views: 759

Answers (2)

suffix
suffix

Reputation: 11

Create your own String (or Suffix) class, as in

http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html

Upvotes: 0

janos
janos

Reputation: 124734

You can certainly invent an Abstract Data Type to represent a "suffix array":

  • Initialized with String
  • Stores the String it received and nothing else
  • Provides accessor methods as necessary, for example:
    • size()
    • get(int n) - return the n-th element
    • equals(int n, String s) - compare the n-th element with input
    • ...

Depending on the functionality you expect from this structure, it might make sense to store the underlying String in a different format, for example as a char[], or even both. It doesn't really matter, that will be an implementation detail, encapsulated, hidden from users of your ADT. Start by creating an interface and define the method it needs to support.

Upvotes: 1

Related Questions