Adds brute force approach to pattern matching is slow when we try to match billions of patterns. Let's try to figure out why. So, what is happening if we put each pattern in its own car, then the first dives the first car, then the second car, then the third car, the next car and next car, and that's why it takes a lot of time. Here's a new idea, let's pack all patterns in a bus, and let's drive this bus along the text. But how do the constructors bus? Let me show you how we can construct the bus from multiplied patterns. Let's start from the first pattern and represent it as a pass in a tree. Continue to the next button, continue this next button, and continue this next button. So far it was easy and not interesting. We have four patterns and we constructed for passes from the root of the tree. Let's go to the next one, antenna. Now the first letter in antenna actually already appears on the way from the root it is right here. The second letter also appear away from the root. And then, we need to branch the previous pass into two passes to construct the pass for antenna. Now let's do bandana. So bandana we press it further. And now we again have to branch the pass. Continue with ananas, again branching. And finally continue with nana, branching again. And of what we've constructed is actually our bus. And which is called trie of patters. How do we use this bus? How would we drive? After constructing this bus, how would we drive with along text? Well, you'll use TrieMatching. And we'll drive this whole trie along the text, and at each position of the text, we will walk down the trie by spelling symbols of text. A pattern from the set patterns matches text each time we reach a leaf. Let me show you how it works. So our bus, in now looking at the first letter of the text, p, so if we walk along the edge, labeled by p, the next letter is a, we walk along this edge, the next letter is n, we walk along this edge, and we found that part of pan appears in panamabananas. Next, we move to the next letter of the text and we start my chunk again. A, n, a and now there is no match so at this position there is no match between, patterns and texts. Continue further, n, a. Once again, there is no match. A, once again, there is no match. For m, from the very beginning, there is no match. We continue further. A. Once again, there is no match. Let's try here. B, a, n, a, n, a we came to so we found the pattern, but we have to continue further. Further. Further. Further. Found the pattern again. Continue further. Again found the pattern. And now, there is no more match. So, we found, in a single run on our bus, we found all matches of patterns against the jacks. Actually, I haven't finished yet. We also have to match n, a, s. No. a? No. Now we are done. Our bus is very fast, recalls at runtime of our brute force approach was O text time patterns. Where pattern says the total lens or for pattern. That 's why it was slow the total length of all patterns is huge. In the case when we tried to match reeds against the genome. But the run time of TrieMatching is only o of text time the length of the longest pattern. And typically in modern sequencing pattern, the reeds have lengths only 200, 300 nucleotide. So it looks like finally they are done. Should we go home? We are not ready to go home just yet. Note that trie we constructed has 30 edges. But in general, the number of edges for a trie is O of the total length of the patterns. And for the human genomes, the total length of the patterns will be in trillions. So unfortunately, our algorithm will be impractical for read matrix. Should we give up?
