Video 6-1: String Matching Intro
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-17, 9:40
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:03 So starting with this unit, we'll look at the most prominent type of data that is around. Everything is a string in the web. Everything's encoded as text. And of course, you know, computer memory is kind of the same. There's also a string of bits if you want to see it that way. And so there's a few standard repeating tasks that these uh representations for data always call for. The first one that we look in look at in this unit is called string matching or finding patterns in in texts. I called it the what's behind controlf the universal shortcut and there's a version on Mac and there's some find in page on all browsers and so on. Um most most programs have this baked in because it's so useful to be able to search um or a small pattern where it occurs on the screen or in a longer text. And uh we have sophisticated algorithms to that do that very very fast. Now that's what we'll look at here.
1:04 Uh before we get there um I'll introduce a bit the terminology that we use for strings and then we'll we'll visit some some classic algorithms that solve this problem. And each of them teaches a little of a different lesson. So I think they all have their place and it's worth knowing about them. We won't spend equal time on all of them. As I mentioned, a bit of notation first. I think people know what strings and text are. But to speak about them for mathematical proofs, remember the eternal truths of algorithms and so on. We want to describe them in a slightly more mathematical set theoretic language as you would have seen it in uh formal language theory as well. So a string is is just a sequence of individual characters. It can encode anything and everything um more or less directly but uh there's many examples of things that are encoded in text including ourselves if you count DNA DNA sequences as text.
2:12 Now, of course, these many different applications call for different kind of algorithmic questions, but one that repeatedly occurs is what I already mentioned, string matching. The task to find exact occurrences of some short snippet in a longer text notation for strings, they're based on an alphabet. I don't know why the S like sigma came for alphabet initially. maybe for symbols, I don't know. Um, in the context of strings, sigma, this capital sigma is any finite set of characters that we're allowed to choose from. And we'll usually denote with little sigma the size of the alphabet. So, the number of different symbols. Most of the time we'll think of the alphabet just as being the numbers zero up to little sigma minus one just because that's the the natural way how you would represent them in a computer and often times is without loss of generality that you assume an integer alphabet. Of course, we interpret them often slightly differently as letters in in actual natural language text or uh maybe including all the uh favorite emojis you may know then uni-ode characters are a bit more than just letters but it could also be very restricted just binary or say the nucleotides of DNA.
3:39 Uh you can always specify this. Then we'll use the notation sigma to the n which in set theoretic terms is the cartisian product of the set of the set sigma n and ffold with itself. That's nothing but the length n tupils formed over this this ground set. Um complicated terms for saying that we pick n letters and change them in a linear linear sequence. And often used are these these shorthand notations. Uh sigma with a power star says you can take any number any number n including zero. So this includes the um all all finite strings you can form over an alphabet and sigma plus excludes the empty string. This little epsilon or bar epsilon if you type it in latte is the empty string. So the string with no characters um we'll we'll use it in that not in in with that meaning without uh with a classification. So keep that in mind doesn't pop up a lot in this chapter.
4:50 Uh more importantly um this is maybe u different from how mathematicians would prefer it. um I denote strings as if they are arrays of characters and I mean they are array of arrays of characters if you represent them in a computer. So we use the standard index notation zero based as usual. Uh we'll borrow the shorthand of writing two strings next to each other to mean the concatenation one string after the other. Uh Python would have this with a plus and Java as well. Um in math notation it's conventional to put a multiplication instead.
5:29 Then we can pick substrings just borrowing the same notation as for arrays. So there's really nothing to define. It's the same as in arrays. You can take uh any such range from I up to J exclusive. Um taking I I then means you take nothing because you start at I but you exclude I itself the end point. So that's always the empty string. Uh the only new thing here is these two names that will reoccur all the time. The prefix I prefix. Uh a prefix of a string are the first so and so many characters. Prefix doesn't say how long just that it starts at the beginning. And suffix the same. It ends at the end with the last character.
6:12 Any others we will just call a substring. I think in this unit this won't occur. We'll use it later sometimes for brevity not here questions up to this point is this somewhat standard I think it's a a mixture of two kind of cultures either this the array based world or this uh set theory based world I tried to pick the best of With that we can define this string matching problem that we want to solve a bit more more precisely. And so here again uh the characters I'm using here come up all the time. So keep keep those in mind. There's a text of length n. That's the long text that we search in. And then there's the pattern of length m which is this the text we're searching for. So usually think of this text maybe being thousands of characters, entire books or maybe even all of the web. Not for this unit but in principle it can be large whereas the pattern is something you type in in the little box that pops up when you hit control F. So usually just a a few dozen characters at most.
7:34 Uh the output um for this unit will mostly look at the version where we find the first occurrence of the pattern in the string formally the first index at which the pattern occurs.
7:50 So starting index so that when you start at this point and reading m letters to the right then you get the pattern and this can be any of the starting positions where this is possible right so that you don't stick out at the end of the text. And if there's no occurrence at all, we return a special no match error code if you like. Or um I'll I'll leave this in the pseudo code as just having a special value no match. Uh if you look in the literature, you always find either this or that variant. The other variant being reporting all of the occurrences. So somehow reporting all of them one after the other. We'll do the first only and then you can call the function again if you need to get all the occurrences. Most of the time that's without loss of generality. I'll point out where it isn't a bit later. So a small example here's a text. It may involve spaces space characters. So we should have put vis vis visible spaces here. And maybe the first pattern is for he. So what would the result be?
9:00 I'm scanning the text from the left and the first occurrence of he is here. Now because we start at zero that's uh index one is the starting position of the pattern 0 1 2 and so on. So I find this here where um the string who doesn't occur. Okay, that's precisely what um both p Java and Python have built in. And I guess most languages have some somehow built in um the precise way how we defined it matches what they also do. They give you the first occurrence.
← Video 5-8: Closest Points in the PlaneVideo 6-2: Brute force string matching →