. So Knuth-Morris-Pratt is a linear time
algorithm, we can't, surely we can't do better than that, can we?
Well, it's not the end of the story. Now we're going look at the Boyer-Moore
algorithm. And it's also a very simple idea that's extremely effective in
practice. So here's the idea.
Instead of matching the pattern against the text moving from left to right in both
pattern and text. Boyer-moore said, what, what if we try to
scan the characters in the pattern from right to left?" so, then, when we find a
mismatch we can skip, we know all the characters in the pattern.
So, for example, if we're looking for a needle in the, in a haystack, if we first
look at the last character in the pattern, which is an E, and we find that N in the
text. Now then, it's clear that the next
possible match is when the Ns lined up, Cuz if it was any other lineup, it'd be
all these characters that we know are not N, compared against N, so we might as well
just move it so the Ns are lined up. And that's good but that's not as good as
the next case. If we happen to run into a character
that's not in the pattern, then we can just skip all the way over.
We don't have to compare any of our pattern character against that one.
So we can just add m if we have m-pattern characters.
And so then in this case we have a more complicated situation.
We match the E, and we have a bunch of Es, And so, part of the algorithm is to figure
out, when you do match a character that's in the pattern and that what do you do.
But the intuition is, it's fast, because you're often going to have this kind of
case where you find a mismath. And since you're going from right to left,
that's you know, that, there's character in the text that's not in the pattern at
all, you can shift over N characters at a time.
And that's a huge win in a lot of practical situation.
So, So how much do we skip?
So the, the first case is clear. If there's,
If you run into a text character that's not in the pattern, then you just move I
from wherever it was to one character beyond the current one that you're looking
at. So, and that's an easy, easy calculation,
it's just increment it by the number of pattern characters that you've not looked
at. Now, but if you have a character in a
pattern then, You want to align the text and in this
case, with the rightmost pattern, and, and that's pretty good.
But you don't always want to do that. If you for example,
We have a mismatch on E. If you were to say, oh, let's line up on
the rightmost most E on the pattern, that would involve backup.
So you don't want to do backup. In that case, you just move on by one.
So there are times when the heuristic is no help.
So what you really want to do is just increment by one in that case.
So just given, those basic preliminaries, It's, clear that it's, actually easy to go
ahead and precompute, how much, you might want to skip.
So, you start out with, with -one. So this is the, amount, that, you're going
to increment the, the text pointer. N - one means you just it's not in the
pattern, so you're just going to move on one.
And so all you do is go through the pattern,
And so let's start with N. So we want too fill in this table for N.
And it says, so if we, if we are going to find an N in the text, what do we want to
do. Well we want to move to the next text
character sorry, we want to co, compare the next text character against this one,
which is zero. And so right of path.charAt j = j.
It's going to, just going to fill in that zero.
Then we go to j = one for the E, E, D, L. it's same, so for what happens is
for if you do that for every letter in the pattern, if you have a letter that appears
more often it gets overwritten until the right most occurrence is the one that's
there. So, that precomputation is just one path
through the pattern. And then giving that precomputation and,
again we're going to implement, this is an implementation of Boyer-Moore, for using
for loop incrementing in the text characte. And so we, are going to have the
text pointer I. I in the course of the algorithm, we're
going to compute a value skip which is the amount that we're going to move the text
character. So we go all the way through the pattern
from right to left. If we get all the way through the pattern
and we find a match, and we don't change the value of skip, then we've found a
match. If we don't, sorry, if we get all the way
through the pattern and don't find a mismatch.
It's all matches we don't change the value of skip and we found a match.
If we do find a mismatch than we're going to compute the value that we skip, which
is where we are minus that table that thing that we computed.
And that's the amount that now that we're going to add to the text character to take
care of the mismatch for the right to left mismatch. and if it's, it's, always going
to be at least one, but if this thing is negative, we're not going to back up.
That's, that's it. So it's a very simple implementation based
on this idea of moving from right to left and skipping over the whole thing if we
find a mismatch. And the key thing about Boyer-Moore you
can study that implementation and figure it out easily, but the key thing is that
this mismatched character here is, takes time proportional to N over M.
That's kind of amazing. We had started out with a brute force
which was N N, And then we got linear time, we were happy
with N, but actually there's a lot of practical situations where you can do the
search in N over M. The longer the pattern gets, the faster
the search gets. It's not only sublinear, it gets better.
That's kind of amazing. Now there's a caveat there because there
is a worse case that could be as bad as the brute force.
So this is just a example of the worst case where you go from right to left,
let's say, and always get to the first character before finding the mismatch, and
you can't do anything better than move over one.
But actually, what you can do is build something kind of like Knuth-Morris-Pratt
to make sure that you don't do something like this with a, repetitive pattern.
And you, you can get the worst case to the linear,
But it's really of importance for, for intermediate length patterns with, because
you so often are going to be able to get this N over M performance.
And that's a widely used algorithm. The Boyer-Moore algorithm.