Please help code the Pattern Matching class below and make sure the j unit tester work as well

------

import java.util.List; import java.util.Map;

public class PatternMatching {

/** * Brute force pattern matching algorithm to find all matches. * * You should check each substring of the text from left to right, * stopping early if you find a mismatch. * * @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 bruteForce(CharSequence pattern, CharSequence text, CharacterComparator comparator) {

}

/** * 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 kmp(CharSequence pattern, CharSequence text, CharacterComparator comparator) {

}

/** * Builds failure table that will be used to run the Knuth-Morris-Pratt * (KMP) algorithm. * * The table built should be the length of the input text. * * Note that a given index i will be the largest prefix of the pattern * indices [0..i] that is also a suffix of the pattern indices [1..i]. * This means that index 0 of the returned table will always be equal to 0 * * Ex. ababac * * table[0] = 0 * table[1] = 0 * table[2] = 1 * table[3] = 2 * table[4] = 3 * table[5] = 0 * * If the pattern is empty, return an empty array. * * @throws IllegalArgumentException if the pattern or comparator is null * @param pattern a {@code CharSequence} you're building a failure table for * @param comparator you MUST use this for checking character equality * @return integer array holding your failure table */ public static int[] buildFailureTable(CharSequence pattern, CharacterComparator comparator) {

}

/** * Boyer Moore algorithm that relies on last occurrence table. Works better * with large alphabets. * * Make sure to implement the last occurrence 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 the pattern * @param comparator you MUST use this for checking character equality * @return list containing the starting index for each match found */ public static List boyerMoore(CharSequence pattern, CharSequence text, CharacterComparator comparator) {

}

/** * Builds last occurrence table that will be used to run the Boyer Moore * algorithm. * * Note that each char x will have an entry at table.get(x). * Each entry should be the last index of x where x is a particular * character in your pattern. * If x is not in the pattern, then the table will not contain the key x, * and you will have to check for that in your Boyer Moore implementation. * * Ex. octocat * * table.get(o) = 3 * table.get(c) = 4 * table.get(t) = 6 * table.get(a) = 5 * table.get(everything else) = null, which you will interpret in * Boyer-Moore as -1 * * If the pattern is empty, return an empty map. * * @throws IllegalArgumentException if the pattern is null * @param pattern a {@code CharSequence} you are building last table for * @return a Map with keys of all of the characters in the pattern mapping * to their last occurrence in the pattern */ public static Map buildLastTable(CharSequence pattern) {

}

}

--------

import java.util.Comparator;

/** * Comparator that allows for comparison of characters and * counting said comparisons. This MUST BE USED for character * comparisons. Using any other form of comparison for characters * will result in test failures. * * DO NOT CREATE ANOTHER INSTANCE OF THIS CLASS */ public class CharacterComparator implements Comparator { private int count;

/** * To be used when comparing characters. Keeps count of * how many times this method has been called. * @param a first character to be compared * @param b second character to be compared * @return negative value if a is less than b, positive * if a is greater than b, and 0 otherwise */ @Override public int compare(Character a, Character b) { count++; return a - b; }

/** * Returns the number of times compare has been used * @return the number of times compare has been used */ public int getCount() { return count; } }

---------

import org.junit.Before; import org.junit.Test; import java.util.ArrayList; import java.util.Arrays; import static org.junit.Assert.*; public class PatternMatchingTest { private CharacterComparator comp; @Before public void setUp() throws Exception { comp = new CharacterComparator(); } @Test public void basicTest() { String text = "The quick brown fox jumped over the laxy dog"; String pattern = "quick"; ArrayList answer = new ArrayList<>(Arrays.asList(4)); assertEquals(answer, PatternMatching.bruteForce(pattern, text, comp)); assertEquals(44, comp.getCount()); reset(); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(13, comp.getCount()); reset(); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(44, comp.getCount()); reset(); text = "aaaaa"; pattern = "a"; answer = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4)); assertEquals(answer, PatternMatching.bruteForce(pattern, text, comp)); assertEquals(5, comp.getCount()); reset(); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(5, comp.getCount()); reset(); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(5, comp.getCount()); reset(); } @Test public void exceptionTesting() { try { PatternMatching.bruteForce(null, "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.bruteForce("a", null, comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.bruteForce("a", "a", null); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.bruteForce("", "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.boyerMoore(null, "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.boyerMoore("a", null, comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.boyerMoore("a", "a", null); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.boyerMoore("", "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.kmp(null, "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.kmp("a", null, comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.kmp("a", "a", null); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.kmp("", "a", comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.buildFailureTable(null, comp); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.buildFailureTable("a", null); fail(); } catch (IllegalArgumentException e) { } try { PatternMatching.buildLastTable(null); fail(); } catch (IllegalArgumentException e) { } } @Test public void edgeCaseTest() { String text = "Whoop"; String pattern = "Whoops"; ArrayList answer = new ArrayList<>(); assertEquals(answer, PatternMatching.bruteForce(pattern, text, comp)); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(0, comp.getCount()); text = "Whoops"; answer = new ArrayList<>(Arrays.asList(0)); assertEquals(answer, PatternMatching.bruteForce(pattern, text, comp)); assertEquals(6, comp.getCount()); reset(); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(6, comp.getCount()); reset(); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(11, comp.getCount()); reset(); pattern = "leer"; text = "rrrrrrrrrleer"; answer = new ArrayList<>(Arrays.asList(9)); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(17, comp.getCount()); reset(); text = "ababababababa"; pattern = "ababa"; answer = new ArrayList<>(Arrays.asList(0, 2, 4, 6, 8)); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(17, comp.getCount()); reset(); text = "shellsellsalesaloonsolesoul"; pattern = "sole"; answer = new ArrayList<>(Arrays.asList(19)); assertEquals(answer, PatternMatching.bruteForce(pattern, text, comp)); assertEquals(33, comp.getCount()); reset(); assertEquals(answer, PatternMatching.boyerMoore(pattern, text, comp)); assertEquals(16, comp.getCount()); reset(); assertEquals(answer, PatternMatching.kmp(pattern, text, comp)); assertEquals(33, comp.getCount()); reset(); } private void reset() { comp = new CharacterComparator(); } }