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; } }

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) {

/*

* This main method is a stub.

* It does nothing.

* Feel free to write your own code to test your implementation.

* In this case, we have nothing actionable in here, just this comment block, so the JVM should rapidly lose interest and move on to the rest of your code.

*/

}

}