As usual, it's very instructive to take a
look at the simplest brute force algorithm
for the problem.
We'll look at that in a little detail,
because it illustrates, really what,
fundamental issues involved with getting
efficient algorithms for this.
And it's also the basis for more efficient
algorithms.
So the brute force method, we could give
in a beginning programming class.
You have your text, you have an index I
that index as in to text, and you have an
index j that indexes into the pattern.
And, start out with both i and j at zero,
and you compare text to pattern, and you
keep going until you find a mismatch.
If you find a mismatch before the end of
the pattern, then what you do is move the
pattern over one position,
That corresponds to simply incremental the
text pointer.
And then, here we have a mismatch right
away, so we move the pattern over one
position, increment the text pointer.
And then starting with I at two, we
compare the second text character with j
of zero, the first pattern character.
Increment j to one, increment i to three,
we have a mismatch.
Mismatch happens at j and +J, j. the jth
character the pattern versus the iJ +
character of the text.
Now we have a mismatch, move over.
That's increment i to three, compare the
first character of the pattern, j = zero
would be the i plus j pattern of the text.
That's a mismatch.
Move over one.
So we go first one is a match.
The second one j of i is four compare
against five, that's a mismatch.
Move the pattern over one, that's a
mismatch.
Finally get to i = position six, and we go
for j equals zero, one, two, three, all
matches.
When j gets to four, which is the number
of characters in the pattern that's when
we know we've found a match.
So, in this table, the entry's engraved,
just there for a reference.
The black ones are where when we found
matches, and the red ones are where we
found mismatches.
So, that's, we do the trace before the
code, because the code is extremely
simple.
So this is, to implement brute force
substring search, to look for a pattern, a
given pattern, in a given text, or for job
as index of, this woud be, on the index of
method in, string, takes the argument
pattern. So we get the pattern length, and
we get the text length.
And we're going to potentially look at
every, straight, the pattern could start
at any position in the text from zero to N
- M.
And for every value of i, we've create a
new j and we look for the match between
the pattern in position j and the text
character of position + j.
If we get all, all the way to j = m, then
we found a match in i.
If we get a mismatch, then we get a break
before j = m, and we go and try the next
value of i.
And if we get all the way through there
without returning, then we just return N,
which is one past the index of the last
text character, the length of the text.
And that's an indication that the pattern
was not found in the text.
Very straightforward implementation of the
pattern match algorithm.
Now, the key point is that,
This algorithm is fine in, in many
contexts, and actually it's the one that
Java's index of uses.
But the real problem is that it can be
slow. Number one,
Just the algorithmic problem,
It can be slow if there's a lot of,
repeat, repetitive characters in the text
and the pattern.
For example, suppose, that the, text is,
all A's and a B, and imagine that there is
a million A's and a B or whatever.
And then the pattern also was a smaller
copy of the same thing, all A's and a B.
Then what happens in this case is that for
every possible position matching the
pattern against the text, we go through
all the pattern characters and only find
the mismatch on the last one.
So,
And then we find a mismatch, we have to go
over one and try them all and find the
mismatch in the last one.
And we eventually do find a match, but for
every text character we've looked at
almost M - one pattern characters.
So, this is a worst case that shows that
the running time of the brute force
algorithm can be proportional to M  N,
where M is the pattern length.
And the pattern could be long, say that
the pattern could be hundred characters
and N can be huge, like a billion and
that's going to be slow,
Particularly by comparison to the
alternatives that we're going to look at.
Now a more important issue than just the
worst case performance is the idea of
backup.
As I mentioned, for lots of applications,
if we're going to put our machine in, on
one of the wires of the Internet and watch
the input go by or if we just take the
abstract standard input model, you don't
get to go, you don't get to back up when
you find a mismatch but the brute force
algorithm is always backing up.
If we go through, matching our pattern
against our text,
When we find a mismatch,
We say we want to move the potential
pattern over one position,
But that means backing up in the text.
So, we would that's, ways to deal with
that by, saving the most recent M text
characters that we've seen.
But it's definitely problematic for larger
patterns and certainly inconvenient. so
the brute force algorithm uses backup.
And so you could maintain a buffer as I
mentioned,
But what we're going to look at is an
ingenious way couple of ingenious ways to
avoid having to do backup.
To setup for that,
We're going to look at,
A slightly different implementation or
alternate implementation of brute force.
It, it,
Compares the same characters as the
previous, implementation.
But, it, does things in a slightly
different order, without, without a second
for loop. And it does the explicit backup,
so let's look at that.
So, we have our i and j pointers, and, and
we initialize them both at zero.
And so it's a for loop where, I gets
incremented on every iteration through the
loop.
And so what we do is, as long as we see a
match we also increment J, so that while
the pattern is matching we're implementing
both I and J.
When we see a mismatch what we do is just
subtract.
The current value of j from i the pointer.
That's the next, character that we have to
look at.
So, when we find this mismatch, we wanna,
subtract the current value of J.
Then increment I at the end of the four
loop.
And that puts us right on the, next, text
character that we wanna look at and then
we reset j to zero.
So this, does the same, Character
comparisons.
But it explicitly shows that we're backing
up in the text.
And then, if we ever get to the end of the
pattern then we return I minus M.
Which is the position of the first
character in the text that matches the
pattern which we found there was M
matches.
So it's an alternate implem,
implementation that will come back to.
So, the ideas that there are a couple of
out rhythm challenges even though this
brute force method, is simple it is not
always good enough.
And so the first one is just, from a
purely algorthmic stand point.
This is a challenge.
Do we need N  M?
Or M is the length of the pattern?
Or can we do it in time independent of the
length of the pattern?
What we want is a linear time guarantee.
And that was a fundamental problem
algorithmic problem that people worried
about.
And for a, for a, for a bit and we're
going to look at the, how people approach
this fundamental algorithmic problem.
And then there's the practical challenge
of we don't, we might not have the room or
the time to save the text and actually the
judge might not be happy about us saving
text away in some computer.
So we want to avoid backup in the text
stream.
All we're supposed to know about is our
pattern.
And we're supposed to light the light if
we find our pattern and that's it.
So what we're gonna see next is a way to
deal with both of those challenges at the
same time.