import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
* Your implementations of various string searching algorithms.
*
* @author YOUR NAME HERE
* @userid YOUR USER ID HERE (i.e. gburdell3)
* @GTID YOUR GT ID HERE (i.e. 900000000)
* @version 1.0
*/
public class PatternMatching {

/**
* Knuth-Morris-Pratt (KMP) algorithm that relies on the failure table (also
* called failure function). Works better with small alphabets.
*
* Make sure to implement the failure table before implementing this method.
*
* @throws IllegalArgumentException if the pattern is null or of length 0
* @throws IllegalArgumentException if text or comparator is null
* @param pattern the pattern you are searching for in a body of text
* @param text the body of text where you search for pattern
* @param comparator you MUST use this for checking character equality
* @return list containing the starting index for each match found
*/
public static List<Integer> kmp(CharSequence pattern, CharSequence text,
                                 CharacterComparator comparator) {

   if(pattern == null || pattern.length() == 0){
         throw new IllegalArgumentException("Cannot search in a null pattern");
   }

   if(text == null || comparator == null){
         throw new IllegalArgumentException("Text or comparator is null");
   }

   List<Integer> lst = new ArrayList<>();

   int n = text.length();
   int m = pattern.length();

   if(n < m){
         return lst;
   }

   int[] failure = buildFailureTable(pattern, comparator);

   int i = 0;
   int j = 0;

   while (i < n && (m-j) <= (n-i)){
         while (i < n && j < m && comparator.compare(text.charAt(i), pattern.charAt(j)) == 0) {
            i++;
            j++;
         }
         if(j == m) {
            lst.add(i-j);
            j = failure[j-1];
         }else if(i< n && j<m){
            if(j == 0){
               i++;
            }else {
               j = failure[j-1];
            }
         }

   }
   return lst;
}

/**
* Builds failure table that will be used to run the Knuth-Morris-Pratt
* (KMP) algorithm.

Problem description: To compare performance of different sorting te...