package algs63;
import  stdlib.*;

/* ***********************************************************************
 *  Compilation:  javac SuffixArray.java
 *  Execution:    java SuffixArray < input.txt
 *
 *  A data type that computes the suffix array of a string.
 *
 *  % java SuffixArray < abra.txt
 *    i ind lcp rnk  select
 *  ---------------------------
 *    0  11   -   0  !
 *    1  10   0   1  A!
 *    2   7   1   2  ABRA!
 *    3   0   4   3  ABRACADABRA!
 *    4   3   1   4  ACADABRA!
 *    5   5   1   5  ADABRA!
 *    6   8   0   6  BRA!
 *    7   1   3   7  BRACADABRA!
 *    8   4   0   8  CADABRA!
 *    9   6   0   9  DABRA!
 *   10   9   0  10  RA!
 *   11   2   2  11  RACADABRA!
 *
 *  WARNING: This program assumes that the {@code substring()} method takes
 *  constant time and space. Beginning with Oracle / OpenJDK Java 7, Update 6,
 *  the substring method takes linear time and space in the size of the
 *  extracted substring. Do NOT use this code with such versions.
 *
 *  See <a href = "http://java-performance.info/changes-to-string-java-1-7-0_06/">this article</a>
 *  for more details.
 *
 *************************************************************************/

import java.util.Arrays;

public class SuffixArray {
  private final String[] suffixes;
  private final int N;

  public SuffixArray(String s) {
    N = s.length();
    suffixes = new String[N];
    for (int i = 0; i < N; i++)
      suffixes[i] = s.substring(i);
    Arrays.sort(suffixes);
  }

  // size of string
  public int length() { return N; }

  // index of ith sorted suffix
  public int index(int i) { return N - suffixes[i].length(); }

  // ith sorted suffix
  public String select(int i) { return suffixes[i]; }

  // number of suffixes strictly less than query
  public int rank(String query) {
    int lo = 0, hi = N - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      int cmp = query.compareTo(suffixes[mid]);
      if      (cmp < 0) hi = mid - 1;
      else if (cmp > 0) lo = mid + 1;
      else return mid;
    }
    return lo;
  }

  // length of longest common prefix of s and t
  private static int lcp(String s, String t) {
    int N = Math.min(s.length(), t.length());
    for (int i = 0; i < N; i++)
      if (s.charAt(i) != t.charAt(i)) return i;
    return N;
  }

  // longest common prefix of suffixes(i) and suffixes(i-1)
  public int lcp(int i) {
    return lcp(suffixes[i], suffixes[i-1]);
  }

  // longest common prefix of suffixes(i) and suffixes(j)
  public int lcp(int i, int j) {
    return lcp(suffixes[i], suffixes[j]);
  }

  public static void main(String[] args) {
    String s = StdIn.readAll().replaceAll("\n", " ").trim();
    SuffixArray suffix = new SuffixArray(s);


    StdOut.println("  i ind lcp rnk  select");
    StdOut.println("---------------------------");

    for (int i = 0; i < s.length(); i++) {
      int index = suffix.index(i);
      String ith = "\"" + s.substring(index, Math.min(index + 50, s.length())) + "\"";
      // String ith = suffix.select(i);
      int rank = suffix.rank(ith);
      if (i == 0) {
        StdOut.format("%3d %3d %3s %3d  %s\n", i, index, "-", rank, ith);
      }
      else {
        int lcp = suffix.lcp(i, i-1);
        StdOut.format("%3d %3d %3d %3d  %s\n", i, index, lcp, rank, ith);
      }
    }

  }

}