Video 6-9: The LCP array

0:02 In the next section, we'll look at this very last criticism from the previous round where I said, "Oh, suffix arrays, they uh they can't do all the magic tricks that suffix trees can." And it turns out that's ultimately wrong. You can make them as powerful as suffix trees, but you have to work a little harder uh to go to get there. And the first very crucial step is what's called the LCP array, the longest common prefix array. uh which gets you a good way towards supporting most of the things suffix tree can do and uh we'll build a bit more on that uh because it's a while ago I thought I I'll leave this one in um one of the early applications of suffix trees which um I guess uh you may guess at this point you cannot easily do with just the suffix array um was to find these longest repeated strings Uh okay, I started it now for real and then you can log in the answer if you want.

1:07 Uh that algorithm to find the longest or say the length um to be precise just the length of of a longest repeated substring. Uh we use some other feature of suffix trees beyond just the sorted order of suffixes. Um which one might that have been?

2:17 Is one of you still thinking? Shall we wait for a short bit as this might be it'll uh the memories will come back. Yeah, but you got it.

2:41 Uh, it's for just knowing the length. All we need is really the string depths of the internal nodes because every internal node has at least two leaves below it. Otherwise, it wouldn't be there. And so, it corresponds to a string that shows up twice. And that's an if and only if if you think about it. So uh finding any node with deepest string depth correspond to a longest corresponds to the longest repeated substring. For that we need these string depths. Now the suffix arrays don't have those. Um here's again how we did this in in suffix trees. Uh just have the picture again. [snorts] Suffix suffix arrays by themselves don't have this. So we'll add something so that this information uh is present again and that's the LCP array. Uh you should think of this as visiting the leaves in left to right order and then between any two adjacent ones say um these two as an extreme example but fine between any pair of adjacent leaves there's precisely one uh lowest common ancestor there's one internal node that splits these and that's the lowest common ancestor in the tree if you walk up there are paths to the root will join at some point. And that nodes string depth is what we're interested in.

4:08 Uh and that turns out to also be the longest common prefix of these suffixes that start at those two positions. Because again, think about it what it means in the suffix tree. If you traverse with that with the suffix starting at one from the root down here and the suffix starting at six from the root down here, they share a path until they don't. At that point they split and that must be their longest common prefix. That's the number of characters they have in common.

4:42 And so um the algorithm for finding the length of a longest repeated substring could be just find the maximum in the LCP array full stop. That becomes trivial. But of course that is once you have the LCP array which for now we've just defined but I haven't told you how to find it.

5:04 Um yeah again the important point is that we compare the suffixes in the sorted order. So in a way the memonic should be longest common prefix. We want these to be really long and they are maximally long if you compare strings that are close in the sorted order. They tend to share a lot. That's the order in which we uh write them down. And as a nitpick, the LCP array for in my for notation starts at one whereas all the other arrays start at zero because it takes um the leaf of uh the the suffix of a certain rank and the previous one and I can only do that starting at one. Uh what you really want to think about is that the LCP array sits between the leaves. It's a bit annoying. You can't write that more conveniently down with 0.5 as indices. That's what it conceptually should rather be. Uh there's another nice connection I want to show in this picture. Here's the leaves and the suffixes that correspond to them. And here are in the sorted order between each pair of adjacent suffixes. Uh there's the longest common prefix written down in red. Then the LCP array is the length of that shared prefix. That's LCP um by definition.

6:29 Now you can uh from this array say there's a certain range everyone shares the empty word as a common prefix. Some ranges say this range also shares the a as a common prefix. And then there's a subrange here that also shares a and n as a common prefix and so on. Um so you can draw what uh is shared as common prefix. And if you now add the suffix suffix tree again suppose we have it uh then you see these these ranges of shared common prefixes one to one correspond to internal nodes in the suffix tree. uh specifically the um like in in this case it's important to say if there's a longer shared prefix that has the same extent it's shared by the same set of leaves then you only look at the longest there'll be a single internal node in the suffix tree for ban not for the intermediate steps that would be unary nodes but in a way this already shows you if you have the leaf array and the LCP array you kind of have the suffix tree at your disposal because these intervals where the LCP is above a certain threshold that corresponds precisely to internal nodes in the suffix tree.

8:06 [snorts] So it's uh LCPs are useful way beyond the simple finding longest repeated strings. um they can indeed reconstruct the suffix tree. And I want to make this more explicit and give you the actual algorithm to compute the suffix tree from these two arrays, which also is a a good opportunity to close for good one of the fi of the black boxes that we left open previously. Namely, how to linear how to find a suffix tree in linear time. I've told you for suffix arrays how it works. I will tell you how it works for LCP arrays. Just give me a a few more minutes. Um but once we have these two, we can construct the suffix tree from those two without much further uh complication. So conceptually a suffix tree algorithm which is I think more efficient than many of the previously known direct ways to compute the suffix tree would be to find the suffix array, compute the LCP array. We'll see how to do that soon.

9:13 And then from those two compute the suffix tree. How do you do this this third step? There's a cute inefficient way to describe it recursively. So I'll show you that on the example. And then there's an efficient maybe even cuter way to do it but is a bit less transparent. So that's on the next slide.

9:36 Here's the leaf array. That's the leaves of the suffix tree we're trying to build. Um, we'll essentially just work on the LCP array though and the recursive meth method says uh there's going to be a minimum in the LCP array. Initially that has to be zero because can't be negative and uh there have to be some strings where at least here I'm adding these dummy sentinels um at the beginning and end of the LCP array to have zeros for good. So the minimum will be zero and it might occur several times. Specifically, there's a zero here and a zero here and a zero here and here and the dummy zero here. That's going to be the top level split for essentially the root. So there will be a root. I'm drawing it a bit elongated so that the uh labels the the uh edges to the children are a bit um easier to see. And we'll recursively apply the same procedure to all the ranges between the red lines. Um but then uh what you get back from this is added as child to the root.

10:58 Okay. And so here, still to compute, still to compute, still to compute. [snorts] And this could be uh an individual single leaf. And of course, we'll have always this one because it's the dollar, but okay. Yeah, you may forget about this. Um, doesn't matter. Let's recurse on on this part where we'll um we'll only look at these guys now. So the minimum here is the one and you can again pretend to have dummy ones at the outside. So I'm not going to draw the uh red lines another time but kind of you always have the boundary at the left and and right end or upper and lower end. So the next the next division here will be between this and this part and we'll have an internal node sitting here that has the five as one of its children and the other child will be recursively computed here.

12:13 Let's keep recursing. So now instead of this we're looking just at these two entries and these three leaves. Again we're finding the occurrences all occurrences of the minimum value. There's just the two. So here we look at this range and that means there's an internal node here that has the seven attached to it. And well guess what? But if you're recursing on one with a single LTP or entry that can only get one more internal node connected like this. Okay.

12:47 Uh this recursive call is also trivial. This single um note with these two attached. And here we have another simple one with three leaves. This one will come first. So it'll have to look like this.

13:11 And that's the the tree topology. So you should tilt this on the side or flip it to the other side. And then you'll see it it matches exactly this tree. It's the same topology just mirrored to the right. So uh flip it vertically.

13:30 Now this algorithm uh is is fine but it's not so efficient because the trivial way to do it would be to rescan the LCP array to find the occurrences of minima. Uh so that may not be so efficient. Um you can avoid this by going through the LCP array once from left to right and build the the suffix tree for a prefix of the string or that's not right. a prefix of the leaves and LCP array entries and in each step just add one more internal node and one more leaf and that works in total linear time. Then um the technical way to do it uh I was fighting a bit with the best way to write it down and I decided to do the insertion in the edge in the end because it's still cleanest. uh you start with um a single vertex to hold the single leftmost leaf. Then the crucial invariant is that we maintain on a stack the right spine of the tree. So if if that is your your current suffix tree, I'm going to keep these two guys. That's the right spine. And I'm following the rightmost child pointer down until I reach a leaf. These two I'll keep on a stack from bottom to top. So root downwards.

15:01 Then when I get the next LCP array value uh the LCP value that tells me how deep the next node has to go in the uh hierarchy of the tree. It could go up here or it could go between those two or it could go down here. And each case gives a slightly different tree. Uh in this first case, in this first case we would have the new node as the new route and essentially the rest of the tree is a left sub sub uh sub tree. Uh now I regret that I drew it so big.

15:58 and there's one more one new leaf that also comes into existence. That's for part A. That's if the new node has a smaller LCP value than all the previous ones. Um, another option would be it's between this and this. Then you would keep the original root. Then you would have the new node. Then you would have this left child here that still hangs here. Um, as I write this, this guy is missing. So there's the new note here. >> You have to tap this.

16:37 It's my reminder that time is running out. E. So here, that's the new leaf. That's the new node. That's the same from previous. You're essentially inserting into this edge the Pulling the edge to the right and plucking in a new node. And then the left here is unchanged.

17:07 And the third option is similar. Uh in each case all you have to do is essentially bend spend away uh constant number of pointers. Um you have this one from the parent down here and from this the child. That's what you have to change. Um, and in the code, what you do is you uh pop from the stack the right spine until you find the spot where you're supposed to go, and then you insert your new node there. And because you're essentially pushing every node once and popping every node once, whenever you do effort, it could be that some insertion takes a longer time because you have a long spine to work up from. But then all these nodes are gone for good and you can't have another expensive step afterwards. In a way, what you're doing with the stack is scattered over time one traversal of the tree. So it's linear time overall.

18:06 I should say the algorithm only outputs the shape of the try and doesn't label the edges with the correct corresponding characters. But that's easy to fix. You can look into the text and uh pick the right edge labels. um easiest conceptually to do this in a second traversal. And as you may have recognized or not, who knows, this algorithm is similar to some other uh known algorithms. Um and you if you want you could say this the topology of the suffix tree is the cartisian tree of the LCP values. If that helps you then great. Um if not fine uh ignore it like a um the algorithm works without that understanding.