Video 6-5: The Knuth-Morris-Pratt Algorithm
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-17, 21:37
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:01 In the next section, we'll look at the canmor algorithm. You've seen these names before. I've cited them twice for having two different insights. It turns out there's a third that they came up with and that concerns this one disadvantage that the string matching automata had, namely that they need a lot of space. And the space was really just for storing the transitions of this automaton. So if you insist on having a deterministic finite automaton, this this is inevitable. It turns out though we don't really need such an automaton. This is not written in stone. If you free yourself from uh the narrow core set of the automata theory motivation, we can do better. So that's what I said. We need all those transitions and that's the best possible we can do for a DFA because I have so many different characters and they might lead me to different places and they do in principle lead me to different places.
1:02 But remember this state X that we traced before when constructing the automaton. We precisely did that. we had took one step with this state X and then said ah from there we just copy the entire column of the transition matrix why don't we just not do that instead of uh copying this entire column of the matrix just to save us one step let's do that on the fly so we can we can uh do this last step of the simulation during the matching and thereby by sidestep storing the matrix in the first place. And what you get um intuitively is a different type of automaton that is not a classical DFA in in the normal sense. If that normal sense was not very familiar to you in the first place, maybe you have an easier time here. Uh instead, you have these um mismatch transitions or failure links.
2:05 Uh which just means I was sitting in this state. I was hoping to read a C, but something else came. So I cannot follow the C edge. Instead, I have to take this failure link. But I'm not consuming this character C yet. I still want to read the same letter C. But I'm trying it again from a different state. And in this case, if I try to read a C from state uh okay, C would have worked. a a letter B from state five. I would take the failure link because I can't read a B from five. But now from three on I can read the B. So I would go to four. That that's the idea. We have a special kind of arc from every state that tells us if you can't read this character just follow that failure link and try again with the same character. And um it's it's already obvious that this reduces the space because only one failure link from each state. So remembering one number per state is enough as opposed to the whole column with uh the entire alphabet.
3:16 Uh so how does this work as an automaton? Almost the same as for the other ones. Um if you want to see the animated version, it's also here.
3:28 So it's the same example as before. Um we start in this state zero. Then we read the text in the same way. Uh if we find an A, then we can follow the match edge to the next state. Now the B we can again follow the match edge and the A as well and the B as well and the A. But now for the B that we see in the text, we cannot follow this link. So we have to use a failure link and then from there try again and here it it works. The next character in the text is an A again. We can follow that. But now we would have wanted C and instead came an A. So we have to take a failure link. And here we can still not read an A. So we have to take another failure link and another failure link all the way down to the start and then we can finally read our A.
4:21 Okay. And if you keep going then uh you may at the end either read your entire pattern or maybe run out of text. Same here on the slides. Same example. Um what it means is that um you may go through an entire sequence of uh of states until you can read a f the next character.
4:54 And to hammer in that that point not just in the concrete example, let's look at the worst possible case. And this worst possible case is worse over all possible patterns and over all possible states you are in the automaton. So uh think as pessimistic as you can.
6:16 Okay, anyone still busy thinking? Typing? Three, two, one. Uh, somewhat split between the expensive options down there. Um maybe let's Okay, here here you go. Let's uh briefly talk about this part. Um what's the worst possible that can happen? The nature of the failure links is that they always go further to the left. They cannot stay in the same place. That would never help us because then we would try to read the same character. the way they're defined. I mean, okay, maybe we haven't formally defined them yet, but they also never jump forward. So, each failure links takes you strictly to the left. You can certainly at most go m times strictly to the left before you run out of left. There's nothing further to the left. Uh so m is the maximum m minus one. Now the question is can this arise? Is there a way to make make this worst case happen? Uh and indeed there is maybe see So the worst case happens if you have a pattern that is all A's and then maybe one B at the end and a text that's all A's. Then of course the first few transitions just go all the way through.
7:57 Now you would like to read a B, but the text comes with an A. And that's not the worst case, right? I need the text to have this. Uh, let's put it somewhere in here.
8:15 Take a few more A's on the other side. This is really something better to be done with the keyboard. Uh, but the the main principle is illustrated by this automaton. Should have more A's here.
8:36 Having a pattern that has all A's gives you an automaton where the failure link goes just one step back. If then also your text is such that you essentially go a long way to the right before you now would want to read a B then uh you have to follow one failure link and you can't read the B follow the next failure link you can't read a B and so on and so on and so on and so on and so on. Okay. So the worst case can be uh attained but you cannot do more than m because you strictly go left. Now that's bad though. If every match of the text might take up to m failure links, we're back to n* m. So what happened here? Did we make did we break this? The trick here is that no this cannot happen. An individual character might need m steps. But every step that we take a failure link brings us further to the left. So I cannot have two such expensive things in a row because before I can go left again, I need to go right first. And the right steps are always single steps to the right. So there's an amortization argument going on that precludes these expensive steps from happening all the all the time. Uh I'll we'll we'll argue this a bit formally and I'll I'll show you the intuitive version in a sec as well. Uh let me first pin down the code for doing what we've shown on the example matching in the failure link automaton.
10:19 There's some procedure to compute the failure links which we haven't spoken about yet. But then if we have that, we start at some position in the text and we start at state zero in the automaton. And then while we still have characters to read, we check if we have the match edge. Then if so, we increment the position in the text and we increment the state. We go one further to the right. If that brings us to the final state, then we return the starting position. We're now at position i in the text. Subtracting the number of characters we've matched gives us the starting index. Otherwise, if we have a mismatch, we have to follow a failure link. Uh we only do that if we're not in state zero, which already means we couldn't match anything, so we might as well stay. Um so if we have a proper failure link, then we follow the failure link. So we update the state to the failure link target. Question Uh yeah, that's the difference number number of outgoing edges in in short and the cleverness here is is just to reduce the space.
12:36 Okay, if you have to follow failure link, you just do that and then uh you don't increment I. So you try to read the same character in the text again, except if you're in state zero, then you can always consume the character and not make progress. That's the algorithm doing exactly what I've shown you in the example. So nothing nothing new there. Uh why does this um overall not use n * m overall steps but actually 2 * n if the pattern is at most uh as long as the text well I guess this is this is unconditional we've not counted what the failure links computation uh needs in principle this is a bit dangerous there's a while loop that may not make progress and uh I don't always increment I and I might do stuff with Q but um only occasionally do I have a step in I so I might have many many iterations of this loop. Uh the argument why we cannot have um too many of these iterations is that in each iteration one of two things happen where we make progress in some sense. Either we increment i, which is we go to the next character in the text.
14:00 We can only do that n times because there's only n characters. Or we increment this quantity i minus q by making q at least one smaller. Whenever we update Q to a failure link, this new entry is strictly to the left, strictly less than Q. So I minus Q becomes one bigger. And that means the position where we start with the pattern is shifted one to the right. And that also cannot happen more than n times. Uh in the animation I tried to show this. That's the part that got uh scrolled out by the zoom. Let me try to show this again here.
14:46 Maybe not on this completely degenerate example or famous one. Uh so try to just look at these um things here below. Each step either makes progress in the text position or it makes progress in how far the pattern has shifted. Um there's never ever any iteration of the Y loop where both stay the same. But both bars can at most become full meaning take n steps. So together combined we do at most these two n iterations uh formally spelled out here. So the total time for this matching part is linear in n factor m even though individual steps might be expensive.
15:34 Now there's only one thing left which is computing the failure links and given how we derived those that they were so close to the string matching automaton. It shouldn't be surprising that the computation is essentially the same as when we computed the string matching automaton. It is exactly this failure state X that we had before. So we're doing the same simulation and just remember the previous X in fail of J and that's it. So um let me show this first and then maybe quickly look at the code.
16:21 Remember what we did back then? Uh we always had this idea of simulating the constructed automaton on the one shorter pattern where we left off the first character. So there's nothing to do really for the first character. the first failure link always goes back to zero. There's nothing else I could go. Now, um when I look at the pattern AB, so I'm looking at the failure link. Um okay, this is still for the first. Let's uh skip that part. Um we're now looking at uh uh that's already giving the the update for that one. Okay. Uh the pattern the the state that we need X for simulating it on the single B is what will become the failure link of A B when we don't read the A but something else okay so simulating the automaton for B means not making a step so X stays at zero that's why the failure link for B points to zero where X was from the previous state.
17:32 The beginning is a bit degenerate. Let's look at the next state. We're trying to find the failure link for state three. This is the state where we've read ABA and now we would want to read a B, but we may not see a B. So, we read something different. But where would we be reading only BA?
17:52 Well, we start here B and then A. We already know that we're before the A in state X. That's how we inductively constructed it. So we take one step with X, follow that transition to state one. So X now is at state one. That's where it would have been reading BA. And so we set the failure link from three to the state where currently X is. That's state one. Then again we update where where X would go with the next character in the pattern following the B to two which means the failure link for four goes to two and so on and so forth. uh in the code what we do is we go through the pattern. We remember the previous X state as the failure link target of this current state and then uh we do an update step which for X either is following the uh match edge from X then we uh increment X by one. If we don't have a match edge, then we have to follow failure links as long as we have to before we can match again. So while the while we cannot follow a a match edge, we either um follow a failure link or if we're in the beginning, then setting this to minus one so that with the increment afterwards it's at zero.
19:24 Okay, that computes the failure links. And again, you may be worried that this is a nested loop. m iterations of the outer loop and potentially more iterations of the inner loop. But by the very same argument as before, uh it's also the case that this outer loop always makes x larger and this always makes the progress on the failure links.
19:51 So x is incremented once per iteration of the for loop in the outer loop and the y loop always decrements x. It can only decrement X if it was incremented before. So in total it cannot decrement here with setting X to fail of X by more than it was incremented in total. So the two together again sum up to two times the length of this thing. In the animation also the bars are shown in the same way. So here uh you also see um how often x was incremented and how often x was decremented and each of them either one of the two makes progress. They can at most reach m each so 2 m in total.
20:44 Now you'll look at this computation of failure links in the tutorials again. Um I promise afterwards it'll look a bit less mysterious. uh summing up the two parts pre-processing on the pattern and the matching part even including the pre-processing this is in terms of bigo as much time as we need to just read the text and the pattern so this is clearly best possible I have to read the text and the pattern to know whether the pattern occurs um at least in the worst case and so uh that's a worst case optimal algorithm Also the space compared to the DFA substantially reduced at least for large alphabets where this makes a difference. Now we only need to store the failure links which is roughly as much space as we need for the pattern itself. So we doubled the space for the pattern.