Today we're going to look at substring
search algorithms.
This is a really fascinating family of
algorithms.
The problem is very simple to state.
And the algorithms we're going to look at
are among the most ingenious that we've
seen, so far.
So it's useful to introduce the problem,
very simple to state the problem.
We have two strings, one we call the
pattern and the other we call the text.
And usually, it's good to think of the
pattern as relatively small, and the text
as relatively long.
In fact, usually we want to think of text
as unlimited length, coming in on an input
stream.
And we have a small pattern, we want to
find out if the pattern occurs in the
text.
So you're doing this.
All the time.
When you do a, a simple search.
On your computer or on the web.
And there's practical applications where,
for various reasons, people want to search
the entire contents of memory or disc for
a particular pattern, to make sure to
check for whether there's something in the
computer that's of interest.
And again, you've got to, such an
application you've got a small pattern and
maybe a huge text.
Or maybe you're looking for your e-mail
which you can think of as a continuous
stream of stuff coming in nowadays, and
you want to look for patterns that might
indicate that there's spam and certainly
you're all familiar with these types of
patterns.
And so what we want is to be able to
identify the pattern quickly and
efficiently in a huge text file.
That's the, one of the most important
indicators of skipped spam, I guess.
.
Okay.
So we'll try to set this up.
This isn't really a real situation but
it's not too far actually.
And so we're going to have these few
characters to try to point out the kinds
of issues that might be involved.
So imagine an Internet surveillance
situation.
Where there's a need to monitor what's on
the Internet for needs of security.
But there might be a, a judge saying, wait
a minute, you can't be looking at all
Internet traffic.
That's private information particularly
among private individuals in, in the U S
for example.
Well,
So what about if we just look for this one
pattern, that, we really need to know
about and that, that, really shouldn't
violate anybody's privacy, like tank or
dorm.
And the Judge can say, okay, how about if
you build a machine that just looks for
that?
And that's what we're going to talk about
today, actually.
One of the techniques that we look at is
perfect for, actually building hardware,
that can, be, put on, a stream of data
passing by, and just light the light if,
that, particular pattern is seen.
So you attach one of those machines, all
over the web, and, if attack at dawn
happens, then you find it.
That's the I would say a simplified
explanation of what it is that we're going
to try to do.
Here's another kind of application.
This is called, screen scraping.
So, we might want to and, and you can do
this, write programs to do this for,
extracting relevant data from a webpage.
And the idea is that there's different
institutions out there that are committed
to providing information on the web.
And they'll promise to, for example this
is Yahoo's page that gives the stock price
of Google.
When you look at the page, it says last
trade but if you write a program to look
at the code that produces the page it also
says last trade.
And since this HTML code is produced by a
program.
It's always going to have the same
structure.
So if we want to find, write a program to
find Google's stock price at any time what
we can do is take this page put it on an
input stream, and search for the pattern,
last trade.
And then just after last pray, trade,
there's the price, in bold.
So what we really want is the string
between, B and backslash B, which delimits
bold, after the first occurrence of the
pattern last trade.
And it's simple to write a Java program
that, implements this.
This is the program, and, the key is,
well, number one, our input.
Standard N, input stream methods.
Allow a webpage, as argument.
So in this case, we provide a command line
argument, which is whatever company you
want the quote for.
And we simple read in the whole webpage.
So now you have the webpage in a long
string.
And then Java.
Has a, what's, index of method for every
string.
And it tells you, where that particular
string occurs.
And so, we'll start at index of last, last
trade.
And then, what we wanna do is find the
first B.
In brackets after that position.
And the first being closed with backslash
being brackets, starting from that
position.
And skipping over the, angle bracket b
closed bracket.
You get the price, and you can print it
out.
Now this is a little utility that screen
scraps from Yahoo's website.
So sub string searching is quite in quite
useful in it's built in as a method in
Java's string data type.
So it's practically useful that's an
introduction.
So now let's look at algorithms for
implementing.
String searching.