Video 6-5: Longest common extensions and suffix trees

0:02 We've used longest common extensions a few times now and so far I've always just appealed to uh your faith in me that there's this black box that magically does it. We'll now peel off one layer of that black box and I'll present you a solution in terms of another black box.

0:22 What do longest common extensions have to do with suffix trees? There's got to be something otherwise they wouldn't be in this chapter. Okay. Uh we've used this uh already a bunch, so I think you uh you don't need the definition another time. Uh how could we possibly um answer this kind of query if we have the suffix tree around? And that's a beautiful combinatorial connection that maybe isn't hard to see. Like if you if you think about these two uh strings, well, they're the beginning of a suffix of the text. So you can start at I and at J reading the text. Uh and if they're sharing some longest common extension, that's going to be a shared path in the suffix tree up to the point where they eventually branch off because there's an internal node and then they split into two different continuations of the suffix. This always has to happen because at the very uh least one of them will end with a dollar which cannot which cannot occur in this in a different position in the other suffix.

1:30 So all we're eventually asking is given two suffixes which is two leaves in the suffix tree what's the lowest common ancestor? That's the same thing. And uh specifically for for suffixes we also have this this third acronym the longest common prefix. So longest common extension is a position some arbitrary pos index in the string. Longest common prefix as the name says is always a prefix and given two strings it's unique what you uh mean by that. Um, and the LCA, the lowest common ancestor, makes sense in a tree. But with the suffix tree connecting, all of the three things are really the same, right? Longest common extensions of a text starting at two positions is the same as the longest common prefix of the suffixes starting there. And this you get from well, the string depth of lowest common ancestor. So, as an example, say we pick these two leaves one and seven. So I guess here my my lovely banana band uh one is this a six seven is this a. So I'm looking at these two uh just visually looking the longest common prefix is going to be two they share a n as the common characters and then one one suffix is is done so they have to differ. How do you find this? Well, here are the two leaves. The lowest common ancestor is this guy and it's at string depth too.

3:11 So, a simple simple kind of connection to see uh but it it will turn out useful for for solving longest common extensions because we can express them in terms of the suffix tree.

3:28 Now, we're left I mean there's there's two black boxes now. We we've gone from uh the single black box of longest common extensions to build the suffix tree which I haven't told you how to do it. And then we also need to find lowest common ancestors which we haven't talked about yet. Now you could take two leaves and just walk up the tree step by step until you meet. That's a way to find the lowest common ancestor for sure. If you you have to think about it a bit cleverly that you don't uh miss each other in a way, but that's clearly doable. You can use the string depth, but it might take linear time because you might have to walk all the way up to the root. So that's not going to get us constant time queries for sure. Uh the other extreme as always with these data structures, right? That's the lazy version. I'm not going to do anything in the pre-processing and do everything at query time. The other extreme is I'm very eager. I'm preparing all the possible uh solutions but that's going to take a lot of space and to compute all those the same goes for the pre-processing. So that certainly doesn't give linear time pre-processing.

4:36 So we need something clever and that's the second blackbox uh which will take us uh to another chapter to solve. um will essentially replace longest lowest common ancestors by arrangement queries and then these will eventually be solved and then there's no more hidden nasty boxes that um that are not resolved. So for the moment we'll we at least got rid of this LCE blackbox and uh from LCE we now know we can reduce it if we have suffix trees and uh LCAS again those two I haven't told too, but they're coming up.

5:38 Let also let me also say a bit um more about suffix trees in practice. Uh as you've seen, they're lovely to construct all sorts of algorithms on paper and whiteboard. If you implement them, uh the theoretical guarantees are good. If you implement them, even though they're linear space and linear time, the overhead is quite substantial. Especially if the alphabet gets bigger, you have to worry about how to represent the edges, the child edges with the labels. Uh, and so by and large, um, people shy away from using suffix trees more and more um because of uh the overhead that they bring. Uh there's direct methods that indeed construct the suffix tree of a string in linear time. Uh but these again uh they're somewhat complicated, certainly more complicated than what I'll show you. Uh and have uh many of them have some some site remarks and asterisks. Maybe they only work for constant size alphabets and things like that.

6:44 Uh so overall um suffix trees rather serve as a good abstraction of what we'll do. We're not explicitly storing them just the way I showed you. But what we'll do is design algorithms in the language of suffix trees and then have another another layer below them how to implement these operations. It's still the best way for me to build intuition how to solve a string problem. I I tend to always think of the suffix tree first because that's easier to work with. Uh but for practical purposes, there's somehow very fat linear time data or linear data structures.