import java.util.Arrays;

public class SuffixArray {

  /**
   * The array of suffixes.
   */
  private Suffix[] suffixes;

  /**
   * Build an array of Suffix objects for the given text String, and sort them.
   *
   * The purpose of sorting is that index(i) just returns the index associated
   * with suffixes[i].
   */
  public SuffixArray(String text) {
    int textLength = text.length();

    suffixes = new Suffix[textLength];
    for (int i = 0; i < textLength; i++) {
      suffixes[i] = new Suffix(text, i);
    }

    Arrays.sort(suffixes);
  }

  /**
   * This nested class represents a suffix of a text string.
   *
   * A Suffix has two instance variables:
   *   - a String reference to the text string
   *   - an int index of its first charecter
   *
   * It also provides four utility methods, namely length(), charAt(i),
   * toString(), and compareTo().
   */
  private static class Suffix implements Comparable<Suffix> {
    /**
     * Reference to text string.
     */
    private final String text;

    /**
     * Index to suffix's first char.
     */
    private final int index;

    private Suffix(String text, int index) {
      this.text  = text;
      this.index = index;
    }

    private int length() {
      return text.length() - index;
    }

    private char charAt(int i) {
      return text.charAt(index + i);
    }

    public int compareTo(Suffix that) {
      if (this == that) {
        return 0;
      }

      int length = Math.min(this.length(), that.length());
      for (int i = 0; i < length; i++) {
        if (this.charAt(i) < that.charAt(i)) {
          return -1;
        }
        if (this.charAt(i) > that.charAt(i)) {
          return 1;
        }
      }

      return this.length() - that.length();
    }

    public String toString() {
      return text.substring(index);
    }
  }

  public int indexOf(int i) {
    return suffixes[i].index;
  }

  public int length() {
    return suffixes.length;
  }
}

@@ -1195,32 +1195,90 @@
 = index;%0A    %7D%0A%0A
+    /**%0A     * Returns the length of this Suffix.%0A     */%0A
     private int 
@@ -1327,24 +1327,88 @@
 dex;%0A    %7D%0A%0A
+    /**%0A     * Returns the ith character in the suffix.%0A     */%0A
     private 
@@ -1464,32 +1464,242 @@
 ex + i);%0A    %7D%0A%0A
+    /**%0A     * Returns a String representation of the suffix.%0A     */%0A    public String toString() %7B%0A      return text.substring(index);%0A    %7D%0A%0A    /**%0A     * Compares two suffixes, for use in sorting.%0A     */%0A
     public int c
@@ -2092,82 +2092,8 @@
    %7D
-%0A%0A    public String toString() %7B%0A      return text.substring(index);%0A    %7D
 %0A  %7D

Add documentation