. And that's still not the end of the story.

We're gonna look at one more really interesting al-, algorithm that has, lots

of important applications, called a Rabin Karp Algorithm.

Invented by two Turing award winners. Michael Rabin and Dick Karp.

I can remember hearing about this algorithm, from my friend, Dick Lipton,

who explained it to me over the phone, and, I, he explained it to me in about,

fifteen seconds, and I realized I had to have this, in the book.

And, so now, here we are, presenting it. Th, that was, in the 70's.

So the basic idea for the Rabin-Karp algorithm is, has to do with hashing.

In it's a particular kind of hashing, called modular hashing.

It's just a particular way of computing a hash function.

It's easiest to think about in terms of numbers, although it, it works in all

kinds of situations. Because remember everything in a computer

is encoded as a byte, which can be treated as bytes which could be treated as binary

numbers. And so what we are going to do is in this

case We saw a pattern characters are decimal digits.

And so, we'll treat a sequence of pattern characters as the decimal number.

And modular hashing is, just take a big prime.

And compute the remainder when you divide your number by that prime.

So in this case, 613 is the remainder that you get when you divide 26,535 by 997.

So you can check that. So that's what we're going to use as the

hash function. And that.

This type of hashing is widely used. You have a prime number, we talked about

it when we talked about hashing. It satisfies, it seems to satisfy

something like the uniform hash assumption under various circumstances.

So that's our pattern, a five character pattern, and we're going to keep the small

hash values 613 and this is going to generalize to longer patterns, and we'll

talk about that in a minute. So now, suppose we have this text.

And our pattern happens to occur here in the text.

And what the method is built on is the idea of you take the first five characters

in the text and compute its hash value. In this case, 31,415, mod down 97, is 508.

So that's different so that's not the pattern.

Maybe take the next five characters, that's 201. That's diffent It's not the

pattern. Take the next one.

That's 715, different it's not the pattern 15,926 by 97 is 971, it's not the pattern.

Eventually, when you have the text characters that are the same as the

pattern characters you're gonna get the same result, it's a match.

If the pattern hat, hash equals the text sub-string hash you, you have the

potential for a match. And that's what the algorithm is based on.

Now it seems like, we're doing a lot of calculation, with, making numbers out of

these things. And, and keep doing modular arithmetic on

it. But actually there's, a really, simple way

to, severely limit the amount of calculation.

And give a quick linear algorithm for, search.

Sub-string search. So first thing is how to compute the hash

function. So we take the, just convert the Math.

So R's our Radix. So in this example, we're using ten so we

have decimal numbers. And then the digits, say t's of i That's

the text characters. So we have a number x of I, which is the,