Video 4-1: §4.1 Introduction

0:03 welcome to unit four of com 5 to6 in this section we'll look at string matching which is finding uh a substring in a longer text and by and large that is what happens if you hit control F in almost any program uh so I think it's it's useful to know what's behind this uh my goals are first to introduce you to a bit of notation for Strings something that we'll use over and over in the rest of the module we'll concretely look at um the canm spread algorithm in detail um the other two boore and ran carp um might have to uh might have to be skipped which in that case would of course mean you don't have to know about them um I also want to cover the performance characteristics of the algorithms that we cover um and this last point is something that I'll I'll come back to uh some of the things that are that have been invented for the string matching problem I found uses Way Beyond that so making that connection I think is very useful and uh you can do some um I hope you can do some simple extensions of this by the end of

1:24 it we'll cover some notation now and look at the the simp simplest way to solve the string matching problem and then next week we'll uh cover the more sophisticated algorithms uh but first let's just talk about uh strings more generally so um starting from from the basics first of all strings are the same as texts but uh one of the two terms is sometimes more more customary to use uh I'll mostly use strings in this use unit uh and later we'll we'll talk about texts as strings that don't change too much mathematically it's a sequence of characters and so you know what a sequence is but characters you still have to somehow Define and that will just be some some finite set of of letters it's the almost Universal encoding for uh for data in com in computer related contexts and uh with large language models maybe even much more than that in a way even even at the fundamental level if you just have bits in a computer memory you can see that as a binary string a bit string so if you want any any data in a computer anything discrete can be can be encoded as a string but we have many more concrete representations that are more specific uh but which are

2:57 strings because it's used in so many different Ms it also means the tasks the algorithmic problems and the solutions um are quite vast and there's different different ones uh we'll cover some some basic ones here specifically we'll try to try to solve the problem if you have a large text which again is just a string but we're we're calling it text to distinguish it from the other string Nam the pattern we're trying to find something in in the long text and so the standard kind of thing you have in mind you have a Word document open and you try to find all occurrences of comp 5 to6 in that document then the text would be the word document and the pattern would be comp 5 to

3:46 six it's the basis of many other applications but also in itself is already useful uh how many of you can can use grab it's a it's a Unix tool to search in files it does control F but the nerdy way if you want uh many virus scanners are essentially doing pattern matching they do more sophisticated things now too but uh they have patterns from known viruses that they scan your programs for as well right let's get a bit mathematical on on making things precise the first thing we need is an alphabet that's a set of characters that our strings are formed from the important bit is it's always finite so we're we're usually assuming that the alphabet can be written down um we say that a string is over an alphabet it could be what you expect an alphabet to be just letters from some script um there's of of course many of them with various various sizes so we'll use capital Sigma for the set of letters and the small Sigma for the number of letters just because that will be a parameter that pops up many many times it's useful to have a a character for that uh it can also be all Unicode characters that's also an alphabet that's relevant in many many

5:12 cases um I think this is how many Unicode characters are there I think it's around 130,000 something like that uh okay I didn't write it down but um I think it's quite a lot so all your favorite emoji all scripts that were ever written on Earth plus konian and um all the useful stuff uh but alphabets can also be small it could be just binary or the nucleotides in your DNA for example uh the basis so many of the algorithms will have to uh to deal with several parameters the length of the string but also the size of the alphabet and uh sometimes we'll have to keep the two in check that's the alphabet and then we have sequences over the alphabet so in mathematical terms this is the cesan product of that set you form vectors or tupal or call them what you want um I'll I'll write them as cartisian products sometimes but the the most common thing you'll find on slides is this notation recess n characters from that alphabet uh and we'll also use sometimes this star or plus maybe the plus not so often Sigma star just means any kind of length so it's the union over all of those now the length of the strings is still finite but uh they can be

6:51 arbitrarily long that's what the sigma star is and the last little one is the empty string which which will uh I'll always denote with this little Epsilon um hope it's always unique is always unambiguous so the empty string is just of length zero has no characters and so it's the same for all alphabets that's the The Only Exception other any other string you have to say what alphabet is from all right the last bit of notations we need is for um talking about individual characters and by and large I will treat strings notation wise as arrays and in computers usually strings are represented as arrays of characters so it's close to how you usually manipulate them anyways um so I'll use the the brackets as before and um it's zerob based as before uh in some other in in some books you also find the subscript so just to make you aware there's operations on strings that we can do we can take two strings and we can concatenate them put the one after the other and this looks like you put s in front of T mathematically is often a short hand for the multiplicative symbol so it became customary to use multiplication as the concatenation for Strings I I'll usually just write it

8:26 like this and the last bit is we can take substrings of a string we can take a range in the in the string and it can be from I up to J including so it's all of those letters um I'll also use that notation when it's convenient so I is included but J is excluded um and last bit is we have prefix and suffix a prefix is a substring that starts at the beginning and a suffix is a substring that ends at the end okay good wake up time uh let's see if that has that has reached you this is not supposed to be a trick question simple quick

9:19 one and you have the formula on your phone so I'll go back to the definitions oops you have not seen right the the overwhelming majority seems to be seems to be

9:58 clear should have hidden the the answers first well for the record uh almost all got this right and so why is it true remember Sigma star these are all the strings of any length and that included the length zero right uh it starts with length zero and the plus is it starts with length

10:41 one so if I take any string I can get any string of an arbitrary length if it either has length at at least one or it has length zero so I've covered all all options here with these

11:24 okay last definition for this part is our actual algorithmic problem so let's also be specific about that uh we have two inputs we have a text it will always be called T and it will always have length n okay try to memorize these uh but they'll they'll come up on the slides many many more times T like text that's supposed to be a big thing that's a book that you try to find something in and then p is a pattern of length M over the same alphabet and usually that is much shorter than the total text but it might still be big so uh it can be searching for a single word but it could also be searching for a bigger pit now what's the output um for this unit we'll find the first occurrence of the pattern in the text it can occur many more times but finding the first one is good enough because we can call the method again starting from looking at the suffix of the text so we can find all occurrences if we want to um but sometimes it's useful to just check if it occurs at all so that's more versatile uh formally if you want to be very precise um the output should be the smallest I in the range of indices from 0 to n

12:46 minus M so that the text if you start at position I and read for M characters that piece of that substring is exactly the same as our pattern so we find the smallest I so that I up to I + m this part that's t i up to I + m that should be exactly our pattern P now sometimes it doesn't occur and then you just return some some special value no match the varant very finded all occurrences thanks yeah

13:55 right it works still the very end where we want to find all occurrences you can can do that iteratively uh let's do a tiny example uh here's your very very long text where is he if you ask for the pattern he then the first occurrence is here and that starts at index one remember we start with zero and if I ask for who there result should be no match okay um I'm aware that you don't normally implement the algorithms I'm going to show you in this in this unit because they already are implemented and so uh you can you can use them but you should know what's behind them to understand the performance characteristics and how long these things might take uh in Java it's string index off and in Python is it's the F method if you have a string uh that that does essentially this first

15:05 one and this is again not supposed to be a trick okay uh we have clear majority for p 526 and that's correct so I tried to show you uh but it's it's very tiny all you really have to do is put the numbers the indices um on top of the letters and then you start reading at index 3 with the p and you stop just before seven and here's that in in