package container;

public class Strings {

    /**
     * Sort an array of fixed-length strings using LSD sorting in O(WN) time
     * @param a The specific array of N strings to be sorted.
     * @param W The length of each fixed-size string.
     */
    public static void lsdSort(String[] a, int W) {
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        // sort by key-index sorting from dth to 0th in the string
        for (int d = W - 1; d >= 0; d--) {
            int[] count = new int[R+1];
            // compute frequency counts
            for (int i = 0; i < N; i++) {
                count[a[i].charAt(d) + 1]++;
            }
            // Transform counts to indices
            for (int r = 0; r < R; r++) {
                count[r+1] += count[r];
            }
            // Distribute the records
            for (int i = 0; i < N; i++) {
                aux[count[a[i].charAt(d)]++] = a[i];
            }
            // copy back
            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
            }
        }
    }


    private static String[] aux;
    private static int R;
    /**
     * Sort an array of strings using MSD sorting.
     * @param strs The specific array of N strings to be sorted.
     */
    public static void msdSort(String[] strs) {
        int N = strs.length;
        aux = new String[N];
        R = 256;
        msdSort(strs, 0, N-1, 0);
    }
    /**
     * Sort the string array in a specific range based on dth character.
     */
    private static void msdSort(String[] a, int fromIndex, int toIndex, int d) {
        if (fromIndex < toIndex) {
            int[] count = new int[R+2];
            // compute frequency counts
            for (int i = fromIndex; i <= toIndex; i++) {
                count[charAt(a[i], d) + 2]++;
            }
            // transform couts into indices
            for (int r = 0; r < R+1; r++) {
                count[r+1] += count[r];
            }
            // distribute
            for (int i = fromIndex; i <= toIndex; i++) {
                aux[count[charAt(a[i], d) + 1]++] = a[i];
            }
            // copy bak
            for (int i = fromIndex; i <= toIndex ; i++) {
                a[i] = aux[i - fromIndex];
            }
            // recursive sort for each character
            for (int r = 0; r < R; r++) {
                msdSort(a, fromIndex+count[r], fromIndex+count[r+1]-1, d+1);
            }
        }
    }
    // return the ascii code of the dth character in the string, or -1 if not in.
    private static int charAt(String s, int d) {
        return d < s.length() ? (int)s.charAt(d) : -1;
    }
}
@@ -2672,9 +2672,1420 @@
 ;%0A    %7D%0A
+%0A%0A    /**%0A     * Pattern search using KMP algorithm.%0A     * @param pat The needle to be searched.%0A     * @param s The haystack to be be searched in.%0A     * @return The begin index of the pattern first found. If not found, return -1.%0A     */%0A    public static int kmpPatternSearch(String s, String pat) %7B%0A        int%5B%5D pmt = computePmt(pat);%0A        for (int i = 0, j = 0, N = s.length(), M = pat.length(); i %3C N; ) %7B%0A            if (s.charAt(i) == pat.charAt(j)) %7B // if matched%0A                i++;%0A                j++;%0A                if (j == M) %7B // found%0A                    return i - M;%0A                %7D%0A            %7D else %7B    // if not matched%0A                if (j == 0) %7B%0A                    i++;%0A                %7D else %7B%0A                    j = pmt%5Bj-1%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return -1;%0A    %7D%0A    private static int%5B%5D computePmt(String pat) %7B%0A        int M = pat.length();%0A        int%5B%5D pmt = new int%5BM%5D;%0A        pmt%5B0%5D = 0;%0A        for (int i = 1, len = 0; i %3C M; ) %7B%0A            if (pmt%5Bi%5D == pmt%5Blen%5D) %7B // if suffix is also prefix%0A                pmt%5Bi%5D = ++len;%0A                i++;%0A            %7D else %7B              // if suffix is not prefix%0A                if (len == 0) %7B%0A                    pmt%5Bi%5D = 0;%0A                    i++;%0A                %7D else %7B%0A                    len = pmt%5Blen-1%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return pmt;%0A    %7D%0A
 %7D

implement kmp