Video 4-2: §4.2 Brute force string matching

0:03 the first string matching algorithm we'll look at is just the brute force method and unlike in some other cases this will already be useful sometimes but of course it's uh it's a bit limited bit of notation um most of the string matching algorithms uh in use and the ones that we look at they use guesses and checks okay a guess is a position in the text position I

0:31 where um the pattern could start and as long as you haven't checked it's a guess that maybe the pattern starts here in the text and initially you have all possible positions as guesses but you can eliminate guesses if you do some uh comparisons and a check is just comparing one character in the text to one character in the pattern and the outcome of such a check might teach you something

1:06 now uh there's a bit of an asymmetry here if um if we want to show that some guess is correct that indeed the pattern starts at position I in the text uh you somehow at least implicitly have to do all the checks all the M checks for all the positions so if you have your guess here then you have to align the pattern to this and then compare character by character and see that they all match whereas to um exclude a guess to uh prove that this P the pattern does not start at this position it might be enough to have one mismatching position because uh well occurring there means all the characters match one incorrect one is enough to debunk that what we'll count is the number of character comparisons so exactly the number of checks uh is is what we'll what we'll count but if you do additional comparisons between the patterns will also count those the number of checks is at most n * m just because I'm I'm assuming if you did a comparison before you remember it you don't do it again so at least the number of different checks is is at most n *

2:30 m and uh the pro Force algorithm just tries all the guesses one after the other and if it ever finds a match it's happy and returns and otherwise it keeps going so you iterate over all guesses try all the guesses I that's all the start positions in the in the text and then you iterate through the positions in the pattern and see if you match at each point so you compare the Chas character in the pattern to the cha character in the text but starting at position I if you ever find that these two characters are not the same then you stop this Inner Loop and continue with the next guess if you uh if you drop out of that Loop and you've reached the end so you could scan behind the entire pattern and all where matches then you can report a match in the text let's do a quick example so here's a a text written on top of this on on top of this grid and we're looking for this pattern

3:36 so what the algorithm would do is it starts looking here let me do this uh a bit slow so we try to align the pattern with this so we would do checks a to a matches B and B matches B and B matches but here we have a mismatch okay so that means we drop out of the this inner loop before we reach jals M no match found we go to the next position of I and we try again to align our pattern here but already after the first character A and B don't match so we move to the next next guess and here the same happens a is again a mismatch and again so you see even the brute force method is often lucky enough that it doesn't have to do all the checks just because it might get a mismatch early on

4:35 and eventually here we have few more but then again the B be a mismatch and so it goes all the way through until it here indeed finds An Occurrence so we've done if you do the count I hope I did it correctly you've done 15 character comparisons in this example whereas the worst case would have been 44 so it it's not always it's not always so bad to use this brute force method and uh I want to point out that Java essentially implements this algorithm with not much uh fuz around it uh python doesn't python had a a project at some point where they invited people to tweak the string matching code and they use something fairly sophisticated now so in this this unit we won't go into the python implementation but there's interesting um articles written about it

5:34 so just to wrap this up um the brute force method can be good enough if your pattern is really short and it often Works reasonably well for for English text where you often if you don't find a match then you often find the mismatch early on uh if you if your strings are completely random it's also is also good but it can be really bad and here's an extreme here's a extreme worst case if the text is all A's and your pattern has lots of A's but then one character at the end that's different then you're actually doing all the checks that that are possible so the worst case is this n * m and uh you should always you should always think of the text being really big but the pattern might or might not be big but if the text is millions of characters and your pattern is a few hundred or thousand that might already not be good enough

6:37 now if you look at this um I mean there there's ways to do much better but those don't come out of nothing if you look at this uh worst case that I've shown you here it definitely has a lot of weird boringness in it self-similarity in the text or in the pattern so maybe there's a way to exploit that and be and and be faster and uh the other the other thing if you if you were to fill out this table uh it's it physically hurts you to write all those A's because you already know from before that they can't match so the algorithm is is horrendously stupid uh by by forgetting everything it learned before and so the second piece where improvements come from is um avoiding that forgetting everything

7:35 just as a a preview we'll look at a few things um how to improve upon this root Force algorithm by spending some time on the pattern first before we start reading the text and uh we'll we'll see a few different ways to exploit that um we'll also come back to this in Unit 8 I swapped those uh to better align with the assessments uh we'll come back to this idea of of string matching in Unit 8 where we'll pre-process the text instead totally different idea but if the text doesn't change this can make a lot of sense so we'll we'll come back to this um but for now we'll focus on pre-processing the pattern