The aim is to write a code in Java to implement the Boyer-Moore algorithm.
We need to integrate the bad character rule with the good suffix rule to produce the complete Boyer-Moore algorithm. The idea here is to use the rule that gives us the better (or biggest) shift in each situation.
Perform the following steps:
- Implement the match() method of the BoyerMoore class, which is available
on the following path:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson5/activity/boyermoore/BoyerMoore.java - Combine the snippets and change the skip logic to choose the best of both rules.
The following snippet shows how the combined matching can be implemented as a solution:
for (i = 0; i < n - m + 1; i += skip) {
skip = 0;
boolean hasMatch = true;
for (j = m - 1; j >= 0; j--) {
if (P.charAt(j) != T.charAt(i + j)) {
hasMatch = false;
skip = Math.max(s[j + 1], j - left[j]
[T.charAt(i + j)]);
break;
}
}
if (hasMatch) {
shifts.add(i);
skip = s[0];
}
}
In this section, we've introduced the Boyer-Moore algorithm as an improvement over the naive search algorithm. By preprocessing the pattern to skip unnecessary shifts, we can decrease the average runtime complexity of the string matching algorithm. In the following section, we will list some other string matching algorithms, listing their applicability, but without going into much detail about their implementation.