Scenario

We have to preprocess string P to build the left array that allows us to use the bad character rule efficiently. Recall that left[i][j] should return either of the following:

• The largest index k so that k <= i and P[k] == j
• -1, if j isn't found in P

Aim

Build an array that allows us to use the bad character rule efficiently.

Steps for Completion

1. Implement the commented part of the match() method of the class BadCharacterRule.

2. Assume that the alphabet of strings P and T consists only of lowercase letters of the English alphabet. Snippet 5.3 is shown below:

   List shifts = new ArrayList<>(); int skip; for (int i = 0; i < n - m + 1; i += skip) { skip = 0; for (int j = m - 1; j >= 0; j--) { if (P.charAt(j) != T.charAt(i + j)) { skip = Math.max(1, j - left[j][T.charAt(i + j)]); break; } } if (skip == 0) { shifts.add(i); skip = 1; } }

   ^{Snippet 5.3: Using the bad character rule to improve our skips}

^{Code Given:}

^{import java.util.ArrayList; import java.util.List;}

^{public class BadCharacterRule { public List match(String P, String T) { int n = T.length(); int m = P.length();}

^{int e = 256; int left[][] = new int[m][e]; // Populate left[][] with the correct values}

^{// Add the code from Snippet 5.3 to search the string using bcr return shifts; }}

^{public static void main(String[] args) { }}

^}

With using the "Code Given" information, add in code from the Snippet 5.3 to search the string using BCR (Bad Character Rule). The Snippet 5.3 is shown in the "Steps for Completion" information.