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
To build an array that allows us to use the bad character rule efficiently.
Steps for Completion
- Implement the commented part of the match() method of the class BadCharacterRule, which is available on GitHub at the following path:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson5/activity/badcharacterrule/BadCharacterRule.java - Assume that the alphabet of strings P and T consists only of lowercase letters of the English alphabet.