Video 9-2: §9.2 LCE using RMQ

0:03 in the next subsection we'll see how the range minimum query problem the first of these abbreviations connects to some of the others that you might hopefully remember from uh Unit 8 we'll we'll come back to those and then that might give you more motivation for studying this more abstract problem the rangement query problem is just on on these arrays of numbers and you might ask why would you want to know the minimum in a certain range what's that good

0:36 for so remember from Unit 8 um there were a few things that we did where the other abbreviations from the section title popped up in um the one first thing was we were looking at suffix trees these beasts um just so that you remember it's the compact try of all suffixes of a text right uh and we were using these for different string algorithms or making different string problems fast one of those was the longest common extensions um problem where we uh this was this was part of of solving uh more interesting questions with suffix trees we we used this as um a building block and then longest common extensions uh could be reduced to finding lowest common ancestors in the suffix tree um

1:36 and uh we wrote that at the time like this so if I want to know the longest common extension of two suffixes that start at position I and J uh then uh I can look in the suffix tree for the two leaves that correspond to those two suffixes and find the earliest where they past join if I move up or the the lowest common ancestor if I move down from the root and the string depth of that node that was uh our longest common extension or the longest common prefix and well we've had this example of uh of the leaves five and seven uh but I think it's too small so if if you want to see the example again maybe we go back to unit eight instead so that's that's the connection between those three things we had longest common extensions of two positions how far can you read to the right in the text and see the same characters from from IJ uh which is the same as the longest common prefix of two suffixes and we connected that to the lowest common ancestor of leaves in the suffix

2:52 tree the second bit that uh is borrowed from Unit 8 was uh this promise that we can do lowest lowest common ancestors LCA queries in trees in a in an efficient way namely in

3:08 in our notation Theta n pre-processing time and order one query time constant time for a query okay so that was the promise back then but I didn't tell you how to do

3:38 it then there's one last thing that we uh studied back then and um that was along along the Journey of getting rid of the suffix tree for our problems instead we used the suffix array then we found the suffix array is not good enough for some problems we also need this LCP array the longest coming prefix array and the longest common prefix array stores uh this longest common extension for two adjacent leaves right remember we had this picture that we walk along the leaves of the suffix tree from left to right now whenever there's a green connection between two leaves they are adjacent in the order of the suffix tree and then we have or in in alphabetic order and for those two we have the lowest common ANC we have the the longest common prefix so the string depth of lowest common ancestor zero here between these two it's string depth one between these two it's string depth two and so

4:53 on so the LCP array as we defined it in Unit 8 already has the uh this the some some ansers for lce queries uh but only if these two leaves are adjacent so I could for example ask for lce of five and seven directly by finding the right LCP entry but if I'm asking for two other leaves that are further apart there's no entry in the LCP array that directly gives that answer but you can translate between the

5:28 two um and for that let me zoom into this this picture a bit and let's find again five and seven these are adjacent in sorted order the suffixes aan and a an there there there's nothing in between there's no suffix that's between the two in in Al lexicographic order that's why the LCP array has directly an entry that tells you the longest common prefix between those two same as what I've just said uh but what if you ask this about an arbitrary collection of two an arbitrary selection of two suffixes um for example I could ask about I could ask about five and one so these are two suffixes um they're not adjacent so what's their longest common

6:37 prefix they span a certain range in in the alphabetic order and they span a certain range in the LCP array as well and the thing is that we have to find the smallest entry in that range to get their overall longest common prefix and the reason for that is if you look at uh the strings these red strings the things that they shap share that adjacent suffixes share uh kind of the lowest common denominator is what determines the longest common prefix between this one and this one so all of those start with an a which means from here to here I have to have at least one thing that they share from here to here I have two which is more than one from here we have even three but the smallest number will always dominate because that means you have the same minimum number all the way through that's the the longest common prefix between those two if there was a longer common prefix then it should be shared among all those in between that's by alphabetic order if these two shared two letters so the first two letters here were the same then anything in between in sorted order also has to start with the same two

7:59 letters so we can we find that the long longest common extension of five and array from well the positions here are numbered a bit awkwardly remember one 2 3 four five and so on so from position two to four

8:40 and that connection is General so if you want to express this in the general case what you get if you have to starting indices of the suffixes the starting index is not the position in this list that's the number in here so the first step that's why that slide is here is to translate from starting index to the position in the sorted list that's the rank array so we take I and J and convert them to their ranks on the right hand side we do that with both now these numbers uh they might not be in sorted order it might be that they swap relative positions by moving to the right that's why we have to take the minimum here and the maximum here and the plus one comes from uh this this convention of the LCP array to sit sit between two suffixes but then it starts with index

9:50 one but overall the connection is is relatively direct you want the longest common extension of two suffixes you need to find the range minimum query of some part in the LCP array all right so again um the connection is is just translating the the pictures from one side to the other um but if if you have things in sorted order and they share a certain common prefix then anything in between has to share at least that much and also if there was anything longer then they would also share this so it's a an exact

10:32 equality so if we um if we translate what that means for um any solution for the range Min rangement query problem to longest common extensions it means that we get essentially the same running time if we have a a p q solution for range minimum queries we can use that solution using the inverse suffix array to directly answer longest common extension queries and we use the same pre-processing time plus

11:13 uh I guess there should be a plus order n because we need the time to compute the suffix array and the inverse suffix array but the query time stays the same um and any interesting pre-processing time will also

11:34 uh will also be at least linear um I think the the cleaner way to express the same thing here is um for longest common extensions when we're already given the rank array and the LCP

12:17 wanted the claim here was we can do it with linear pre-processing and constant query that would be the final goal for the range minimum query problem and you can compare that to uh what your guess was uh what might be