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

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:03 The next step after we've seen how to use the string matching automaton, if we already have it, is to construct this with a a pro a constructive algorithm that tells you what to do instead of reasoning about individual arcs. And again, um this is the part if you've seen this before, we can use a non-deterministic finite automaton instead of a deterministic finite automaton. And that makes constructing the automaton super easy. It's right here. You write the pattern on these edges edges to the right and that's it. A non-deterministic automaton is the same as a deterministic automaton without the promise that there's exactly one outgoing edge per character. uh instead here there may be several edges or there may be no edge at all for some characters in which case you're uh either given a choice and you have to pick one or you're stuck in which case your termination your your computation just dies and terminates.

1:10 Uh the the trick with non-determinism is if there is any way you could have chosen the transitions so that you accept you end up in an accepting state then the automaton accepts and you have to magically know the right way to make the choices.

1:29 That's a convenient vehicle in theory. It is a rather unusful model of computation because I can magically guess. This is not an operation that computers can do. Uh if you wonder where the choice comes in in this automaton, it's hidden in this in this arc of sigma. Uh all that this automaton says, oh uh stay in state zero for an indefinite time until divine insight tells you now the pattern will start. And if you were correct, then you can scan through the entire pattern and accept in the last state. If not, well, tough luck. I'm out of here. Right? That's the non-determinism. Again, as a model of computation, rather bonkers. You cannot really execute that. Uh um but it's easy to construct. Now, finally, you can actually execute it with a trick. You're just simulating all the possible parallel universes you could be in simultaneously. And this sounds worse than it is. Question if we have a a a regular expression or a non-regular. You said what's a non-regular expression?

3:03 I mean if if it's a regular language, it has a regular expression and then the the classical uh automa theory you would do in in TCS tells you how to get from this regular expression to your DFA uh with a powers that construction in between but in general always possible a non-regular expression I think this is not a fixed term. It could be could mean many things and maybe then it's not possible if it's a complicated construction. Uh so here in principle we can work with these nondeterministic uh states. All that we have to do is keep track of all possible states we could be in as a set of states. That's the parallel universes I was referring to. So if we're in state zero, what can I do? Uh well, here's the text. I can read an A, which means I can follow this arc to state one, but I could also stay where I am. So, uh, I'm afterwards in state zero or one. Which one? Well, kind of both. I don't know yet. I'm not going to decide yet.

4:10 With the next step, um, I'm a bit schizophrenic now. I'm in two states. So um I'm adding all the possible successor states that I could end up in and put them all in my list. So with a reading an A, if I'm in state zero, I can go where I am. I I can stay where I am or I can follow this arc to one. But I can also when I'm in one follow an A. But yeah, there is no one there is no arc out of one. So I can actually not do anything here. And had I decided to take this transition to one in the first step, I would immediately run into a dead end. Now, okay, if I'm in these states zero or one and I read a B, I can stay in zero if I'm in zero. Will always stay in zero and can stay in zero. Uh, I cannot do anything else from state zero, but I can do something else from state one.

5:05 But there's note that there's no way for me to be in state one after reading a B. Uh there's not not an option here. If I read another A from zero, I can stay where I am or go to one. And if I'm in two, I can read the A and go to three. And so you see how we can make progress in parallel on on these states. And if any of them is going to succeed, we'll notice. Uh let's continue the example. Well, if I read a C now, well, I can always stay put and I can try to read a C in one or in three, but all of them will fail. So, I'm left with just zero from zero with a an A. The next transition I can stay or I can use a one. Now, I can read another A, which means I can stay or I can read uh the A to one. I cannot move on further. But now with the B I can if I read another A then I can stay I can go to one or from two I can go to three that's a one you see how it gets a bit repetitive and that's indeed the power set construction you declare a new state for every set of states but let's not go there now if I'm in any of these three states and read a B you see from three I can go to four so that's already Good.

6:31 From zero I can always stay. And from one I can go to B to two with a B. Now reading an A, I get from zero to zero. I get from 0 to one. I get from two to three and I get from four to five.

6:56 Now if I read a C now the field thins out again. From five I can go to six but all the others die out. From three I cannot process a C. From one I cannot. Zero stays.

7:09 Okay, one last step. And then we found our pattern. If we read an A, now we get the zero and the one, but also from the six to the seven, we get seven. And that's an absorbing state. So now we found our pattern. Okay, here the same in in written a bit nicer. So in principle, even though I started out saying ah nondeterministic automata kind of not a useful model, you could actually do it. It's um is not completely uh uh hopeless. Of course the number of states that we track here could be up to all states. So up to m states and then in each step I might have to check m states. That's total cost n* m. We've seen that before. That was the brute force algorithm. So it looks like in the worst case we win nothing.

8:09 But stand aside. I know some TCS theory, right? Um if you have a nondeterministic automaton, you can always construct a deterministic out of it. That's the construction I mentioned earlier before.

8:21 Now, in the worst case, this construction has an exponential blow up and so it's even worse than what we've just done. So, uh maybe we'll just stick with brute force. But at this point, um that's the part where you can forget about the automata theory general lesson. It's it gets you that far, but now you can make much more progress by studying the problem specifically at hand. We're not building a generic automaton for an arbitrary regular expression. We're solving this particular string matching problem. And there was a a clever idea um that was put together by by three famous people uh can Morris and Pratt that will show up in an algorithm later. We can instead of doing this generic construction via the NFA, we can directly construct this string matching automaton in an inductive way. And the the clever idea there is that to construct for the next state. So we do this um character by character. We start with a prefix of the pattern. And suppose we've already built the automaton for this prefix. call that AJ.

9:42 Now we're trying to add one extra character at the end of the pattern and construct the next larger automaton. Uh if you see if you remember the examples um here's one.

9:56 If you imagine we've built this this first part up to five and we now add the state six. There's two things we have to do. we have to add the match edge, the one that takes the next character of the pattern. That's easy. We know what what that is. And then we may have to add other um arcs from this new state back into some old states whenever there's a mismatch. But the crucial thing that we worked out here is these these arcs backwards. If you don't match a character, these were all were always going further left. they can never use any of the new states. They're entirely within our automaton AJ. And so we can in principle we can in principle find out where these other transitions go. That's the the formal way to write this. Delta is a transition function that has a state and the next character that you read and tells you what state you should go to.

10:58 So for each uh character which is not the next one in the pattern, we somehow need to figure out where to go. And it turns out you can do this by just looking at the already constructed part of the automaton. So you can inductively build this uh step by step. And what's behind that is precisely what we've used before. Um so this meaning of this new state as before is the length of the longest prefix. So that this is uh what we've seen so far and you can express this as it's the length of the longest um prefix of this this part that we've read that is also a suffix of this part and it's a suffix here where where we start at one not at zero. So to express that it's a strict suffix every string is a suffix of itself that would be not very helpful. And the clever insight is this this equality.

11:59 This length of the longest prefix by definition of what the states mean is the same as the automaton itself would do if we just read this string where we leave off the first character. Let me say that again. We know where we go from any state with the next character by simulating the automaton itself to the point that we've built it so far by leaving off the first character in the pattern. And so um that again we can do I think it's uh worth seeing in action once.

12:42 Let me start somewhere in the middle so that the automaton is not completely boring and tiny. So uh the first step say we have built this automaton for the first two characters. AJ is J is two. A2 is the automaton for the first two characters A and B. Um and now we're is this is up to J is okay the first three characters there's always this off by one in the indexing um there's always the outgoing edge to the match state um mismatch in in the index notwithstanding we're now adding the next character to this partially built automaton that is uh we include this this J. Here we have a match edge to the next uh new state. And what we need to still fill out is the other edges of this newly included state three. That edge is easy. That's just the car next character in the pattern. Right? The pattern starts with abab.

13:58 Okay. The pattern is nowhere to be seen other than here. Do we have the full pattern written somewhere? This is a bit bad. Here's the pattern. Okay, it's the same same boring pattern I was using all the time. A abaca. So, we've taken the next character. The fourth in this in this um pattern is is another B. Adding this match edge is easy. Now, we need to find the other edges. For that uh we take as first other character an A. So we take ab a b a. If you chop off the first character then you read b a b uh sorry b a a. Instead of this b we now read an a. So a b a b a b a a a is the overall text. Now we simulate in the automaton this text without the first character. That's what we're seeing. So we start in state zero. The first thing we read is a B. So we stay. Then we read an A. Then we take the arc. We read another A. So we stay.

15:11 And this point that we reach as the last step. That's where the new arc from state three goes to because that by definition is the longest prefix of our pattern that we could align with this one shorter. So after um after getting rid of the first character the best overlap between a b a a and our pattern is just putting a any other position before had a mismatch. Uh we have another character the c. So now we have a a text a b a c a b a and then a c instead of b. Leaving off the first character means we simulate b a c. So I'm starting here, take the loop to uh that state back. Then we read an A gets us to state one and a C brings us back to zero. So the arc from J with with C goes to zero. Okay? And you do this all the way through um each time. Uh here we have just an alphabet of length three. So one match edge and two other characters.

16:19 That's not as bad. Uh, but you may note that um we're redoing a lot of work here. I don't know how visible this is.

16:39 For both cases, we started with just walking down here and then took one extra step. If you think about it, it's obvious um from the construction here, we always read this entire string and then change the last character in that construction. So if I have many more different characters, I need an arc for every different character in this last position. But I'm always simulating this this entire automaton on this one shorter prefix. But only the last character here changes. So of course the automaton will lead me to the same state after all these steps. So we're still doing something redundant. Um I wanted to point that out right here. We'll come come back to that. Uh the way it's described here seems to require simulating this smaller automaton for every arc. So in total we have m states with sigma rx sigma minus one and for each of them we have to walk through an automaton simulating up to m steps rather expensive in terms of the uh pattern length.

17:53 And the second insight that the same three people had is what I just pointed out. If you're starting simulating this shorter automaton starting with the first character of the pattern and only swapping out the last letter that you append, you'll always repeat the same computation. And to see that again, let me switch here to the uh second version where there's something highlighted. It's the same example, but now we keep track of the state where we ended after reading the the prefix. And so again, let me step forward to the point where we started last time.

18:40 This was the part we we looked at in detail. I add this new match edge and now I have to find where do these two outgoing arcs go to. And the observation is there is some state x so that both of these arcs just follow one outgoing arc from that state x. Namely for a they follow the outgoing arc from x with an a. And with a c they follow the outgoing arc from x with a c. And you're just copying the target of that state.

19:11 Um, one more time here highlighted. So, uh, the match edge is easy. Now I'm I'm adding the B here. The transitions I'm going through for reading BAB is always B A B. So I can remember that I ended up in state two. And then for B, the next edge that I take, that's the target of where this B edge goes. If I instead put a C here, I still have BAB. So, of course, I'm going to end in the same state X. And then I read a C instead of of an A of a B. So here I follow the C edge. In this case, it takes me also to state zero. Could have taken me elsewhere. So by remembering where the state X is, I can do the simulation only once and then get rid of redoing the same computation. And now there's even one more trick. Why even run the simulation to get the final position of X from start each time you add a new new symbol?

20:27 also these prefixes. If I now go to the next thing, instead of BAB, well for the next character, we're going to have BABA. So, they're again sharing the prefix BAB. So, I might as well start where BAB got me to. This is my old X. And I'm doing one more step with A. That brings me to some new X. And from there I can copy the transitions. So no simulation needed at all in the final version.

21:04 Here I'm just carrying over where X would go with the next character. And um this has a very simple to do a simple version that you can do manually very efficiently. Um if you look at the table what what happens is in this next column that you want to fill the outgoing edges from state one you first copy the whole column that uh state X has copy all of the entries that's all of the targets of its arcs and then you overwrite the um match edge with a B you instead go to state One more step. Now you have to update X. X currently sits at zero. Now I'm reading B for X. So B stays in state zero because it takes this arc. Now with that new X, I'm going to copy from X again. The first column chuck into here. Overwrite the match edge and update X.

22:13 And keep going like this. Let me do one more example here. We've traced X to here. That was BAB. You know, again, um we copy wherever X is into the matrix here and overwrite just the match edge. And with that trans with that uh procedure, you can fill out the entire uh transition matrix for this for this automaton very quickly. It's very very quick to do manually if you practice it three times.

22:54 So that's the second insight that the three had that you don't need to do any simulation at all whatsoever in the end just uh carry along this state x that would have resulted from the simulation and copy where its transitions go written out in code that's uh what I've just shown this is doing the copying of the column and then updating one step. If you just stare at the code without that intuition or the buildup in mind, I think it's a bit cryptic. Um, my hope is that now that you've seen it, it's not so hard to do and you can check yourself on the example or make a new example in the animation if you prefer.

23:41 Okay, so uh let's wrap up this this first part. We've done a first version of string matching that for the matching part after the DFA of this automaton is built needs precisely n steps for the text. It steps through one of these arcs. It's one table lookup each. That's almost as cheap as it gets. uh building the DFA we started with something that would have taken uh m * sigma x m and we arrived at something that is just m * sigma which you may note is the size of this transition table you have m * sigma entries there so we're already doing this optimally we take constant time per entry that's the time we need to write it so that's not going to be that's not possible to improve uh the space that we need is the T space for the table. So, um it is what it is. It's probably the fastest in terms of matching time and already essentially best possible unless uh your alphabet is rather large.

24:47 But the space overhead might be rather substantial. The sigma sounds innocent if you think about normal alphabets, maybe 26 or so. But remember, this could be all of the uni-ode characters. And there we're talking 120,000 and counting. Every couple of months someone invents some new emojis. So blowing up the space by a factor a 100,000 is maybe not so great.

← Video 6-3: String matching with finite automataVideo 6-5: The Knuth-Morris-Pratt Algorithm →