import java.util.Arrays;
import java.util.Comparator;

public class TRAII_25_t24_skeleton {

    public static void main(String[] args) {

        // example text
        String text = "abcccaabba";
        System.out.println("Text:" + text);

        // create and print
        Integer[] suffArray = createSuffixArray(text);
        System.out.println("Suffix array:");
        printSuffixArray(suffArray, text);

        // try a couple of searches
        System.out.println("\nSearch:");
        System.out.println("aaa: " + findFromSuffixArray("aaa", text, suffArray));    // no
        System.out.println("abc: " + findFromSuffixArray("abc", text, suffArray));   // from start
        System.out.println("abba: " + findFromSuffixArray("abba", text, suffArray)); // from end
        System.out.println("ccc: " + findFromSuffixArray("ccc", text, suffArray)); // from middle
        System.out.println("abca: " + findFromSuffixArray("abca", text, suffArray)); // no
        System.out.println("ddd: " + findFromSuffixArray("ddd", text, suffArray)); // no

    }


    /**
     * Find the matching index of a key
     * @param key to find
     * @param text to search
     * @param suffixArray of the text
     * @return key match position, or -1 if not found
     */
    static int findFromSuffixArray(String key, String text, Integer[] suffixArray) {

        // TODO

        return -1;

    }

    /**
     * Print a suffix array and the suffixes
     * @param suffixArray suffix array of text
     * @param text original text
     */
    static void printSuffixArray(Integer[] suffixArray, String text) {
        for (int i = 0; i < text.length(); i++) {
            System.out.format("%3d: %3d %s%n", i,
                    suffixArray[i], text.substring(suffixArray[i]));
        }
    }

    /**
     * Create suffix array from text (easy way).
     * There are faster algorithms.
     * @param text input text
     * @return suffix array
     */
    static Integer[] createSuffixArray(String text) {
        int n = text.length();
        Integer[] suffixArray = new Integer[n];
        for (int i = 0; i < n; i++)
            suffixArray[i] = i;

        Arrays.sort(suffixArray, new SuffixComparator(suffixArray, text));
        return suffixArray;
    }


    /**
     * Comparing class for suffix array indexes.
     */
    static class SuffixComparator implements Comparator<Integer> {

        Integer[] suffixArray; // suffix array to sort
        String text; // original text

        public SuffixComparator(Integer[] suffixArray, String text) {
            this.suffixArray = suffixArray;
            this.text = text;
        }

        /**
         * Compare ind1 and ind2 according to the substring they point to.
         *
         * @param ind1 the first object to be compared.
         * @param ind2 the second object to be compared.
         * @return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than
         * the second.
         * @throws NullPointerException if an argument is null and this comparator does not permit null arguments
         * @throws ClassCastException   if the arguments' types prevent them from being compared by this comparator.
         */
        @Override
        public int compare(Integer ind1, Integer ind2) {
            return text.substring(ind1).compareTo(text.substring(ind2));
        }
    }

}