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.