Is so that pattern matching with suffix tries is fast, but impractical with respect to the memory footprint. How about this idea? We saw that bananas takes a lot of edges in our suffix try. Can we compress all these edges into a single edge? That's very easy to do. So let's simply do this, and do this with every known branching pass in our suffix tree. Very quickly our tree gets much smaller. So if you're almost done, continue, continue And finally, we construct something that is called SuffixTree(text). And since each suffix adds one leaf and at most one internal vertex to the suffix tree, then the number of vertices In the suffix tree is less than two times text and therefore memory footprint of the suffix tree which is proportional to the number of edges in the suffix tree is simply all the lines of the text. This sounds like cheating! Because we haven't answered the question, how do we store all the edge labels? They will take the same total length of pattern space that all labels in the suffix tree took. However, let's try to do the following. So instead of storing the whole string bananas as a label of our edge, let's notice that bananas start at the position six of the text and has lance eight. And therefore instead of storing bananas on the edge, we will only store two numbers, 6 at the starting position of bananas and 8 the last of bananas. That will be sufficient to reconstruct the entire label bananas. And we will do it for all edge labels. And as a result, now you see that suffix tree is indeed a very memory efficient way to code all information about suffixes of the text. You may be wondering, why did we add this silly dollar sign? To panamabananas. I added it because I wanted to make sure that each suffix corresponds to a leaf. But why do we want to make sure that each suffix correspond to leaf? I suggest you try to construct suffix tree for papa without adding the dollar sign and compare with the suffix tree for Papa, with dollar sign and you will see why the dollar sign is important. The sos of suffix trees are a fast and memory efficient way to do pattern match. However, construction of suffix trees is not for faint hearted because they need to combine all suffixes of the caps into the suffix tree. And the name of it for doing this takes quadratic O text squared time. However there is an ingenious linear time algorithm for constructing suffix trees called and it was developed over 40 years ago and this algorithm amazingly has linear write of text to construct the suffix tree. So it looks like we are done, finally, after all the effort. And now, I want to tell you about the big secret of the big O notation. Something that Sasha, Daniel, Misha, and Neil, forget to tell you about. Indeed, suffix trees enable fast exact multiply pattern matching run time. All of text plus patterns, and memory of text, that's the best we can hope for. However, Big O notation hides constant, and the best known implementation of suffix tree has large memory footprints of 20 time text which reaches very large memory requirement for long genomes like human genomes. But even more importantly, we want to find mutations. And it is not clear how to develop fast Approximate Multiple Pattern Matching category using suffix tree. So once again we are facing an open problem that we have to solve.