Video 6-10: LCP array construction

0:02 The last missing piece is how to compute the LCP array. We found good use for it now. Um, now we're eager to construct it as well. And clearly it has to be linear time otherwise we're not happy. We have to do it in linear time which means we can't naively just uh compute it uh by scanning. So one option is if you have the the suffix array you could just take your adjacent suffixes and compare them. how many characters are do they have in common and uh write down the number. But in an extreme case, the text of all a again uh each of these steps could essentially be linear time. So quadratic overall no good. We need something smarter and the key idea is best seen on an example. um this this procedure is expensive exactly when the numbers in the LCP array are big. But when that's the case, we actually know quite a bit. Just uh the knowledge is a bit inconvenient um as the way it presents itself. Let's look at a at a long text with a lot of repetition so that there's a good chance for a long shared prefixes prefixes.

1:17 That's this lovely text. Buffalo, buffalo, buffalo, buffalo, which you can add a substantial amount of buffaloos to and it still makes a chromatically correct sentence. Uh, but that's besides the point. Uh, let's say you take the first suffixes of this text in sorted order. First one is just a dollar, but then things become a bit more interesting. There's all these uh guys starting with ALO. Um, I wonder why ALO dollar is missing.

1:47 That's before the space, right? Uh whatever. Um somehow that got lost. Uh there's maybe another character that is not printable, so you don't see it and it messes up the sorting order. Uh let's pretend the text has these suffixes. Uh my point is if you have two suffixes that are adjacent in sorted order and they share a long common prefix, guess what? If you take away the first character of both, they still share essentially the same prefix except for the first character that they both lost. So if the LCP here has a large value, removing the first character gives you another place where there's a long shared prefix. The only problem is that we don't know where that is. And it might even be nowhere at all because who knows if chopping off one character leaves these two suffixes adjacent. Maybe there's another suffix now that smuggles in in between because we've removed a character. A lot of things could happen.

2:53 So this this insight is is useful, but using it productively seems uh to require a trick. And the trick is what uh Casiadal used for for their very lovely algorithm which is just compute the LCP values in a clever order following your knowledge and then you can maximally reuse what you've learned if you ever spend a lot of time following many shared characters. You can profit from that for a good while and produce many big uh LCP values for cheap. So how does that work? Um again my my favorite picture from before the suffixes in text order suffixes in sorted order. Cassideal says just compute the LCP values in text order and everything will fall in place. Let's do that. Uh the first is obviously this one the entire text. Now this doesn't get an LCP value. An LCP value is always between a suffix and the previous one in the alphabetic order. So for knowing what which one that is, we have to move to the right. So we use the rank array and find that we're we're actually working in position six here in the LCP array.

4:15 And the previous uh suffix is this guy. Now initially we know nothing. So we have to pay for finding the shared prefix and here it stops. So we can compute our first we can write down our first LCP value three.

4:33 Now we want to maximally reuse what we learned or maximally reuse the work we have done. So we get rid of the first character which is the same as moving to the next character next suffix in text order. But where is that guy to be found? Well, we have to look at the rank array and find it over here. Now, it has some previous suffix in the sorted order. And we don't know if that is uh ban without b. It actually isn't, right? That one's up here. There's someone else in between. But these two shared a n. These two shared a n. Everything in between has to share a n as well. maybe more but at least these two. So we inherit that these two characters are shared and we can start computing the next LCP value from two onwards. And in this case uh we did get another shared character that wasn't here before. So it's another entry three.

5:35 And we keep going like this. Uh I animated the entire example. So we go to the next uh suffix in text order. find where it belongs here. We inherit the two characters and check if there's more. There isn't here. So, it's just a two. That's it. Going to the next one in text order. Find it over here using the rank array. Inherit one character. Check one more. Another LCP value two. And you keep going. Okay? And that way you see if you ever have to scan a lot through the text, that's fine. But then you're not going to pay in all the subsequent large LCP values much more because you've already made a a good way through the strings.

6:28 It gets shorter and shorter as you go through. And if you write this down as as proper code, uh you get something like this. There's an outer loop for the position in the text. That's the scanning on the left. Then you find where are we on the right. Uh you find the position the starting position of the suffix that is one above you in sorted order. That's the i minus one. And you may have remembered some shared characters L from the previous iteration. Initially none. Uh but you skip the first L characters of these two suffixes when you do the comparison. As long as they are equal, you increment L. Once you're done, L is the LCP of these two suffixes. So you write that one down. And for removing the first character, make L1 smaller unless it's already zero. And then you repeat. I think in code this is even uh even even simpler and maybe maybe subtler to follow than in the example.

7:33 So I hope the order of presentation helps. Uh let's quickly analyze this. That's clearly in the code even even clearer. The dominant operation is the number of character comparisons. And as for sorting, remember from last time, um even it's a while ago. Uh it's clever to compute the number of comparisons you do separately for the ones that come out as equal and the ones that come out as not equal. Uh the ones that come out as not equal are always those that stop this inner loop. And that means there's one of them per outer loop iteration. So linear. So only one per uh value of I. Uh the ones that come out as equal there may be maybe many but they always increment L and L always remains below N and is decremented only by one here. So you can't increment it by more than 2 N over by by N overall. Um I guess 2n overall right? Yeah you incremented once here you decremented once here at most 2n for sure.

8:47 So you have a linear number of character comparisons in the entire algorithm. So the entire algorithm is is linear time as well. Now because these are so useful already, this combination of the suffix array maybe with the inverse suffix array and the LCP array um has been given an extra name, the enhanced suffix array. Maybe it's not a good name, but it is a name. Um it usually means at least these three sometimes uh additional structures and you could say it's the modern version of suffix trees that uh when when you try to solve string problems at scale you would go to uh such an approach as opposed to suffix trees. It is a bit harder to reason about uh at least for me personally um but anything about the implementation speaks for it. Um, one good way to think about them is design an algorithm for suffix trees and then compile it to work on suffix on enhanced suffix arrays. Uh, usually that's is actually not a hard the second step is not hard to do. Uh, and indeed we've seen for many of the things you can do on suffix trees already how to do it.

10:06 For example, string matching we kind of saw except that with a slowdown, but we'll work on that. Um the cross here doesn't mean it's not possible. It's just that we haven't done it yet. Uh we've looked at LCP values. The internal um nodes uh in a suffix tree are essentially the LCP values or these intervals. So we kind of have those. Uh what we haven't looked at is longest common extension queries. And remember from even the the chapter before suffix trees, we've heavily used them for the inexact string matching and we left it as a black box how to do them. So that's up for next time. Uh and there's another um nitpick on suffix links essentially the things that showed up in a-hole corus that you could add easily to suffix trees and we haven't talked about it for suffix arrays but these are these are easy. Uh the main the main open one is this one. And the matching time