Video 6-3: String matching with finite automata
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-17, 14:50
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 Looking at the brute force string matching algorithm shows you two things. It works for typical cases. Whatever typical means for for non degenerate cases, it often works fast. But it had this worst case that is very repetitive. And maybe let me go here again. If you look at this this um example, what happened is that you're comparing from the start each time again. Whereas that this in the text is an A. I already know because the previous pattern matched there and had an A as well. So it makes you maybe feel that there's some some way to exploit this redundancy in the text and in the pattern. And that's what most of the upcoming algorithms will try to do.
0:55 Let me also mention uh what we'll do here is the approach that we spend a little bit of time on the pattern to speed things up to precisely re use such redundancies as we've seen in the worst case for brute force. There's an alternative approach that we'll revisit towards the end of the at the at the end of the module. Um, if the text doesn't often change, say your DNA sequence, then you might rather spend a lot of time processing the text and then ask many queries that uh you can then answer fast. This is an alternative approach that we'll not look at here. So here we we always assume we do this once the text is searched. Now you're in your in your document, you hit control F. Uh we don't expect to search the same text many times. In that case, it makes sense to spend little time on the text and maybe do a little light amount of pre-processing on the pattern to speed things up, but not much more.
1:56 And the first approach uses finite automata. That's why I asked the question here. Let me just for the record show um has shifted a bit since I last showed it. So more people feel um they've not heard of this. Uh all that means is that some of the site connections are maybe uh a bit lost on you. It doesn't affect the actual algorithms much. If you've if you've done formal language theory, then you can recast string matching as deciding whether the text is in this formal language. You can parse this without knowledge from what I've defined earlier. This on the right is the the set of strings that you get by taking any number of symbols in the alphabet. Then append the pattern and then append more symbols from the alphabet. Again, any number. Of course, that's the same as string matching because I'm I'm trying to find an occurrence of P in the text. If there's an occur an occurrence of P in the text, there's some stuff before the occurrence and then the pattern and then some stuff afterwards.
3:04 uh clearly the same. Now the part that that uses theoretical computer science basics is that this is a regular expression. So this set of strings is a regular language and that means this is the part this inference here that's what you would do in in automata theory or formal languages.
3:28 There exists a little automaton, a little machine that is uh able to decide whether a text has this pattern or not, has this shape of the regular expression or not. And it's even a highly efficient machine that looks at each symbol of the text once and just does one one swipe through the text in the same way as the majority algorithm from yesterday. Uh it's a you can see it as a streaming algorithm through the text. So um the theoretical computer science researcher here could say I'm done here because the problem is clearly solved. Just read the textbooks about automa theory. Now maybe not qu not yet. So first maybe that's you the problem zero uh question. But more seriously the fact that this thing exists is not really satisfactory. If you if you're I'm supposed to use this to search, then I need a constructive way to get to this automaton at the very minimum.
4:29 Uh there's a second lurking issue which if you remember this part um we'll step through it again a bit. There's a step if you want this DFA, the deterministic finite automaton. There's a power set construction and power set sounds an awful lot like exponential. So there's a um in principle a potential for blow up so that this automaton is very large and then it would be rather useless. All of these are hypotheticals as it turns out. But there are questions or things you have to look at and address. Let's first ignore that part though and jump to the end. Suppose I give you this automaton already. How does string matching with such an automaton work? Uh here's an example. This automaton is built for this pattern here. And you can see that by following the edges to the right. If you read these uh horizontal edges, the match edges, then you obtain exactly the pattern ab.
5:43 Now for the graphical syntax, um the numbers are just there for decoration at this point. They're just names for the states. The states are these round circles. I can sit in one of those states. That's where I currently am. And then I always follow one of the arcs. There's that's the promise of a of a DFA. There's exactly one outgoing arc for each character in the alphabet. And so I start at the state zero. I read the next character from the text and I follow the arc the uniquely determined arc labeled with that character that takes me to to another state. Uh last bit is if I ever reach this double circle state then I can accept. So I can uh determine that the pattern has occurred which at this point I should remember where in the text I am to return the index. But let's let's do that after that. Uh let's let's step through this briefly. Um maybe we can have the nice animated version.
6:50 I think my drawing of the automaton is nicer, but this is a bit more dynamic. So we start in the zero state, then we read an A. So we should follow this edge to uh state one, right? Uh now we're in state one. The text continues with another A. So we follow the edge that is labeled A. In this case does nothing. We stay where we are. Next character in the text is a B. So we move forward again. And so on and so forth. I think you uh you can imagine how this goes. You may uh stay where you are. You may move forward on the chain or you may move backwards. Uh if you ever reach this this state seven, you're essentially done at this point. you found an occurrence of the pattern up to this this previous um it did one more step right it cheated a bit I I think it should have stopped here at this point we've just seen the last character of this first occurrence of the pattern and so you see here that this is our our pattern that we were looking for so what you get from this is is just this sequence of states and then uh at some point if you ever reach that state seven the sigma arc here means you're just staying there signaling that you've seen seen the pattern our understanding for solving this problem I as I posted finding the first occurrence you can just stop there now um this is wonderful but you may wonder why does this even work and how do I get to this automaton so Let's have a a bit more of a critical look at what happens.
8:33 There's a very simple intuition to this automaton. Maybe you've spotted it in the example. Maybe it's a bit hard to see at first glance. Uh the states, these numbers in the states, they do have an intuitive meaning or a precise semantic. Uh a state Q means I've seen the first Q characters of the pattern. Well, that's obvious because um I've somehow walked to the right. If you if I start at zero and then I see the first four characters of the pattern, then I would have just walked to the right. What's a bit more subtle is even if I in between did some steps back and forth, this is still true. This is a promise so far. Uh nevertheless, there's a a second more subtle part. I've seen these Q first characters of the pattern and no more of the pattern. I cannot have a larger prefix of the pattern that ends here. So it's the largest largest Q that um so that I have seen the the first Q characters of the pattern just here. And if you think about it, this is a bit harder to maintain because if you're in some state and you now don't see the next character in the pattern that you would expect for a match, it's a bit hard to figure out where you have to go because you might have some parts that you can reuse.
9:57 And um in principle one wonders if it's even possible to have such a well- definfined transition for every character even for characters that are not in the pattern say and um to kind of explain why this still works is well we have if we're now sitting at some some u arc some um some state let me pick a more interesting one the three and we now see an a so I'm wondering about this this arc back here. It's hard to see.
10:35 Uh I'm sitting at state three. So I've I've just read aba and that's the longest prefix of the pattern I could have seen here. And now I read another A. That is not how the pattern continues. So I'm I'm in this situation where this first part is aba and c confusingly is an A.
10:55 Let me write this. A B A and this is an A. Now, um I know I've had a mismatch. So, this is not a prefix of the pattern. Otherwise, I would just follow this this edge to the right. Uh so, this I know, which means the longest prefix I can still find will be shorter than Q characters with this Q+ one characters including the C. That's the picture here on the on the right. I want to find a new state so that this new state tells me the number of characters I have seen from the pattern maximally from the beginning but including this new character C which was a mismatch. So this this cannot be longer than the previous part and the crucial observation here is uh these have to match right these are all equal characters including the C. So I know everything about the text that I need to know to determine this this Q prime because it can only depend on parts that are in my prefix of the pattern and maybe this extra character C.
12:11 So this um the full information is there and therefore there's a well- definfined arc that if I read this new character where I have to go is fully determined by this prefix that I've read. Now that doesn't tell you yet where you should go but at least we know there's a unique target that this arc should go no matter what the text looks like.
12:58 Uh C could be occurring elsewhere in the prefix. It does in our case, right? Um the example we had was that we have aba as the prefix. So q is three and c is all is a. So that was the last part of the text. This this uh a b a a and now a is part of this prefix right.
13:32 Uh yes, we have to use that information for the next step. Uh and the way we use it is to find what is the longest overlap I can put my my uh pattern in. So if I have a b a a and something before that as the text, we'll take our pattern and I'll I'll try to have to be ab a b a c a.
14:00 If I was diligent enough with putting the pattern with equal distance between the characters, I could just literally shift this along. So this this didn't work, but maybe I can start here. Ah, no I cannot because uh B and A don't match. Maybe I can start here. The A's match, but this doesn't. No. So, but I can shift it like this. So, I still have an overlap of this first character. So, Q prime should be one because that's the longest overlap I can generate between this part of the text that I have and the beginning of my pattern. And of course you see the arc we were following from three with an A goes to state one which matches this uh value for Q prime.
← Video 6-2: Brute force string matchingVideo 6-4: Constructing string matching automata →