So we're studying Boyer-Moore and we have our bad character rule and we have our good suffix rule. And so far we've used them separately. But in practice, we're going to use both of them together. So basically, whenever we have a mismatch, we're going to try both rules. And each rule will tell us some amount that we can shift the pattern P. In other words, some number of alignments that we can skip. And we're simply going to take the maximum of the two. So let's use them both in an example. So let's say that this here is our first alignment of P to T. The very first character comparison is going to result in a mismatch. This G in the pattern mismatches this T in the text. So since no characters matched, the good suffix rule is not applicable here. There's no matching characters so we can't use the good suffix rule. We have to use the bad character rule. So what does the bad character rule say? Well it says that we should shift until this highlighted T here, is underneath this T here. So this skips six alignments. So it shifts P over by seven positions or it skips six alignments. And the good suffix rule doesn't skip at all, because it's not applicable. So we're going to use the bad character rule in this case, and we're going to skip over six alignments. Okay. So let's do that. Here's our next alignment. We've skipped over six. So here we get some matches, so we have our mismatched character here, and we have our small T, the stretch of characters that we matched within the text. And so, if we use our bad character rule, it's going to tell us that we can't skip any alignments. Because as soon as we shift P over by one, the C down here that's highlighted in purple comes underneath this C right here. So the bad character rule doesn't skip any alignments. The good suffix rule does skip some alignments, so this is GCG. This is the string of characters that we matched within T. There's another occurrence of GCG right here, so the good suffix rule is going to let us skip two alignments. We're going to shift P over by three characters. So we take the maximum, and we shift P over by three characters, skipping two alignments. And we get this. So in the next alignment, the bad character rule will skip two alignments where the good suffix rule will skip seven alignments. So we're going to take the good suffix rule, and that gets us to this point here. So we just solve three steps where we used the bad character rule and the good suffix rules together, and we'll implement this is the upcoming practical session. So you might wonder, how much of an improvement is Boyer-Moore over naive exact matching. So in this example, we went through a few steps of Boyer-Moore and we skipped a total of 15 alignments. So furthermore, there were several characters in the text, these characters highlighted up here, that we completely ignore. They were never involved in any character comparisons that we did. This explains Boyer-Moore's advantage over naive exact matching. Even in the best case, naive exact matching is never going to skip an alignment, and there is never going to be a character of the text T that it fails to examine. So in practice, we do expect Boyer-Moore to be substantially faster. And this is generally true. And we'll explore this a little bit in the homework in this module. We have to address now one last detail, which is that in order to use our rules, the bad character rule and the good suffix rule, we need to be able to look up how far the rules tell us to skip. So the example's we've worked through so far, we've been figuring out how far we can skip sort of by eye. By looking at the pattern P and by thinking about matched or the mismatched characters in the text T. In reality, what Boyer-Moore implementations do is they build some lookup tables beforehand, so that every time we want to apply a rule, either rule, the number of skips can simply be looked up in a table. So, the only information that we need in order to build these tables is the pattern P. The text T is not needed to build these tables. So for example, I'm showing you a table here. This table will help us apply the bad character rule for a particular pattern P. So here the pattern is TCGC, which you can see is labeling the columns of this matrix here. And so how do we use this table, this Matrix? Well let's look at an example. Here's an alignment over here on the right. And we've done two character comparisons. There was a match, C matching C, and then a mismatch, G mismatching T. So the G, at offset 2 in the pattern, that's what mismatched. And the character that it mismatched in the text was a T. So this offset 2, in the pattern P, corresponds to this column of the matrix. And this mismatched character from the text T corresponds to this row of the matrix. So we're going to look in this column, and this row, and we'll find a number there. And that number is the number of alignments that we can skip according to the bad character rule. So in this case, we can skip one alignment, which is to say, we can shift P over by 2 according to the bad character rule. So before Boyer-Moore starts to examine any alignments, first we have to build lookup tables for both the bad character rule, like the table that we can see here, and for the good suffix rule. We won't describe exactly how to build those tables here. But just keep in mind that those are a couple of tables that we have to build beforehand. And the only thing that we need in order to build those tables is the pattern P.
