package package01;

 import java.util.Arrays;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 public class class01

 {

     private Suffix[] suffixes;                                  // 后缀数组

     public class01(String text)

     {

         int n = text.length();

         suffixes = new Suffix[n];

         for (int i = 0; i < n; i++)

             suffixes[i] = new Suffix(text, i);

         Arrays.sort(suffixes);

     }

     private static class Suffix implements Comparable<Suffix>   // 后缀类，包含原字符串和该后缀在原字符串中的起始索引，text[0] = originText[index]

     {                                                           // 每个后缀元素都保存了原字符串，浪费

         private final String text;

         private final int index;

         private Suffix(String inputText, int inputIndex)

         {

             text = inputText;

             index = inputIndex;

         }

         private int length()                                    // 求后缀元素的长度，要用原数组长度减去该后缀的起始索引

         {

             return text.length() - index;

         }

         private char charAt(int i)                              // 取后缀元素的第 i 字符，要用起始索引开始数

         {

             return text.charAt(index + i);

         }

         public int compareTo(Suffix that)                       // 比较两个后缀元素

         {

             if (this == that)

                 return 0;

             int n = Math.min(this.length(), that.length());

             for (int i = 0; i < n; 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 length()

     {

         return suffixes.length;

     }

     public int index(int i)                         // 注意 index 表示后缀元素的起始索引，同时也是各后缀元素的原始序号

     {

         if (i < 0 || i >= suffixes.length)

             throw new IllegalArgumentException();

         return suffixes[i].index;

     }

     public int lcp(int i)                           // 计算排序的后缀数组中第 i 元素与第 i-1 元素的公共前缀长度

     {

         if (i < 1 || i >= suffixes.length)

             throw new IllegalArgumentException();

         Suffix s = suffixes[i], t = suffixes[i - 1];

         int n = Math.min(s.length(), t.length());

         for (int j = 0; j < n; j++)

         {

             if (s.charAt(j) != t.charAt(j))

                 return j;

         }

         return n;

     }

     public String select(int i)                     // 返回排序后的后缀数组中第 i 元素

     {

         if (i < 0 || i >= suffixes.length)

             throw new IllegalArgumentException();

         return suffixes[i].toString();

     }

     public int rank(String query)                   // 查找 query 在排序后的后缀数组中的排名

     {

         int lo = 0, hi = suffixes.length - 1;

         for (; lo <= hi;)

         {

             int mid = lo + (hi - lo) / 2;

             int cmp = compare(query, suffixes[mid]);

             if (cmp < 0)

                 hi = mid - 1;

             else if (cmp > 0)

                 lo = mid + 1;

             else

                 return mid;

         }

         return lo;

     }

     private static int compare(String query, Suffix suffix) // 比较两个后缀类

     {

         int n = Math.min(query.length(), suffix.length());

         for (int i = 0; i < n; i++)

         {

             if (query.charAt(i) < suffix.charAt(i))

                 return -1;

             if (query.charAt(i) > suffix.charAt(i))

                 return +1;

         }

         return query.length() - suffix.length();

     }

     public static void main(String[] args)

     {

         String s = StdIn.readAll().replaceAll("\n", " ").trim();

         class01 suffix = new class01(s);

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

         for (int i = 0; i < s.length(); i++)

         {

             int index = suffix.index(i);

             String ith = "\"" + s.substring(index, Math.min(index + 50, s.length())) + "\"";

             assert s.substring(index).equals(suffix.select(i));

             StdOut.printf("%3d %3d %3d %3d %s\n", i, index, (i == 0) ? 0 : suffix.lcp(i), suffix.rank(s.substring(index)), ith);

         }

     }

 }

 package package01;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 public class class01

 {

     private static final int CUTOFF = 5;    // 插入排序分界

     private final char[] text;              // 原字符串，只保存一份

     private final int[] index;              // 索引数组，序后第 i 子串的首字符是原字符串中第 index[i] 字符

     private final int n;                    // 字符串长度

     public class01(String text)

     {

         n = text.length();

         text += '\0';

         text = text.toCharArray();

         index = new int[n];

         for (int i = 0; i < n; i++)         // 初始化 index，排序交换是对 index 进行的

             index[i] = i;

         sort(0, n - 1, 0);

     }

     private void sort(int lo, int hi, int d)// 基于字符串的第 d 位进行三路排序

     {

         if (hi <= lo + CUTOFF)

         {

             insertion(lo, hi, d);

             return;

         }

         int lt = lo, gt = hi;

         char v = text[index[lo] + d];

         for (int i = lo + 1; i <= gt;)      // 排序后 a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]

         {

             char t = text[index[i] + d];

             if (t < v)

                 exch(lt++, i++);

             else if (t > v)

                 exch(i, gt--);

             else

                 i++;

         }

         sort(lo, lt - 1, d);                // 分别对前段，中段，后段进行排序

         if (v > 0)

             sort(lt, gt, d + 1);

         sort(gt + 1, hi, d);

     }

     private void insertion(int lo, int hi, int d)

     {

         for (int i = lo; i <= hi; i++)

         {

             for (int j = i; j > lo && less(index[j], index[j - 1], d); j--)

                 exch(j, j - 1);

         }

     }

     private boolean less(int i, int j, int d)// 比较

     {

         if (i == j)

             return false;

         for (i = i + d, j = j + d; i < n && j < n; i++, j++)

         {

             if (text[i] < text[j])

                 return true;

             if (text[i] > text[j])

                 return false;

         }

         return i > j;

     }

     private void exch(int i, int j)

     {

         int swap = index[i];

         index[i] = index[j];

         index[j] = swap;

     }

     public int length()

     {

         return n;

     }

     public int index(int i)

     {

         if (i < 0 || i >= n)

             throw new IllegalArgumentException();

         return index[i];

     }

     public int lcp(int i)

     {

         if (i < 1 || i >= n)

             throw new IllegalArgumentException();

         int s = index[i], t = index[i - 1], n = 0;

         for (; s < n && t < n; s++, t++, n++)

         {

             if (text[s] != text[t])

                 return j;

         }

         return n;

     }

     public String select(int i)

     {

         if (i < 0 || i >= n)

             throw new IllegalArgumentException();

         return new String(text, index[i], n - index[i]);

     }

     public int rank(String query)

     {

         int lo = 0, hi = n - 1;

         for (; lo <= hi;)

         {

             int mid = lo + (hi - lo) / 2;

             int cmp = compare(query, index[mid]);

             if (cmp < 0)

                 hi = mid - 1;

             else if (cmp > 0)

                 lo = mid + 1;

             else

                 return mid;

         }

         return lo;

     }

     private int compare(String query, int i)

     {

         int m = query.length(), j = 0;

         for (; i < n && j < m; i++, j++)

         {

             if (query.charAt(j) != text[i])

                 return query.charAt(j) - text[i];

         }

         if (i < n)

             return -1;

         if (j < m)

             return +1;

         return 0;

     }

     public static void main(String[] args)

     {

         String s = StdIn.readAll().replaceAll("\n", " ").trim();

         class01 suffix = new class01(s);

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

         for (int i = 0; i < s.length(); i++)

         {

             int index = suffix.index(i);

             String ith = "\"" + s.substring(index, Math.min(index + 50, s.length())) + "\"";

             assert s.substring(index).equals(suffix.select(i));

             StdOut.printf("%3d %3d %3d %3d  %s\n", i, index, (i == 0) ? 0 : suffix.lcp(i), suffix.rank(s.substring(index)), ith);

         }

     }

 }