CS 566 – Efficient Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-17, 5:39

Click any sentence to play from there.

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:02 has always been an algorithmic problem. Let's try the simplest and easiest solution first. And in a way, that's a brute force approach in this case. Let's just try every possible starting position and find if the pattern is there, if the pattern starts there. Uh to put that in a bit more uniform language, we can say there's guesses and checks. So a guess is a starting position where you where I could guess that the pattern starts there. And a check is just one comparison between in this case the the text and the pattern and it could be at any positions is one symbol comparison. And some obvious observations if you want to verify a guess if you want to check if a guess is indeed an occurrence of the pattern you have to check all the m characters of the pattern. So you need m checks. there's no way to kind of uh speed that fur speed that up further.

0:59 But if you only want to rule out an incorrect guess, maybe you're lucky and a single comparison tells you that it isn't is a mismatch and then you can immediately rule out that specific guess because it matches at this starting position if all characters match.

1:17 Our cost metric for all of this unit uh will be counting comparisons between individual uh characters in the texts or in the strings I should say uh both both text and pattern count of course. Um the number of checks that we do for all guesses is upper bounded by uh doing all the m checks for all the n guesses or n minus m roughly uh but is upper bounded by n * m. So if that number isn't too large maybe there's no need for any fancy algorithms and often you're even with a very simple algorithm faster than that. That's the the brute force string matching method. It does literally what I said earlier. It loops over all possible guesses. Then it loops over the positions in the pattern. It does a comparison of the position in the pattern and the corresponding shifted position in the text. Those that would be in in line. I'll show you the example in a sec. If any of these mismatch, I know the guess is dead. So I break out of this inner loop and continue with the next guess.

2:34 If I finish this inner loop without breaking, I will probably have found um that J is M. So I've checked all of the characters in the pattern and then I can return this current guess as the starting position of the pattern and it will be the first occurrence because otherwise I would have uh returned earlier. If you do this with some madeup strings, even if they have just characters A and B, uh you note that often maybe let me do this a bit bit slower here. Uh so I I guess that the pattern starts at the first position and indeed I find that that is uh almost a match but here the last one is a mismatch. Let me put that in red maybe.

3:29 So I have to compare the first three characters according to this algorithm and then I find out oh it's not a match. But for the next guess I immediately find the A is a mismatch with the B that I'm trying to align with it as I'm shifting. Okay. Now now I'm going too slow. I'm not going to do this for all. But if I put a BBA here and abba here and so on. uh you quickly see here I can stop at the first character. Here I can stop at the first character. So often times here's all the comparisons you actually do. Often times you don't really go through all the M comparisons and um you have to in a way find uh be creative to find an example where this bad case even occurs. And probably that's the reason why Java doesn't do much more than that. Most of the typical inputs are still fast enough with this brute force method.

4:33 Now, not always. The brute force method has a worst case. For example, this one shown here, which is uh admittedly a somewhat boring text, but there are applications where things like this are not so uncommon. and then um you may have a lot of tests, a lot of checks to do uh just to conclude that the pattern does never occur. Now here if you look at this with a bit of a distance of course if there's a B in the pattern and no B in the text we shouldn't uh be surprised and somehow we could have found a quicker way to test that in the text there is no B. But um of course you can modify the example and so on. So on the positive side, it is a very simple method and has very little overhead. If we care about worst case performance though, then this is uh a bit lacking. If if n and m are both relatively large, say n somewhat in the millions or even longer and m a few thousand, this may already be rather annoyingly slow.

← Video 6-1: String Matching IntroVideo 6-3: String matching with finite automata →