Video 9-2: §9.2 LCE using RMQ

0:02 now that you know what the problem is about let's look at some connections why this is interesting you've seen an application of arrangement queries you just don't know it yet we've looked in unit 6 remember the suffix trees and all these things we looked at the longest common extension problem so remember that was given the string or you can read the text of course so it was given a string and then um two positions i and j you were asking what's the longest part that you can read from these two positions to the right so that these two are the same before they're stopped by something where they differ

0:56 and so the length of this thing that was the longest common extension and we've seen that you can use this in the kangaroo algorithm and in other in other algorithms to speed up certain string problems

1:17 at the time we noted the longest common extensions of to the longest common extension of two positions in a string is the same as the longest common prefix of the suffixes that start at that position that sounds complicated but it's just renaming and we've seen that this in a suffix tree like here you've seen this example if we take the suffix starting at one or in position five in banana ban you will see that their longest common extension or the longest common prefix is is just the letter a and you find this this length at this as the string depth of the lowest common ancestor of those two leaves so again lce was the same as lcp of the corresponding suffixes and we found that as the string depth of the lowest common ancestor of two leaves okay so that's the first step

2:17 um and then we've seen that there is our magic black box that we didn't look into at the time that we can find the longest the lowest common ancestor of two vertices in a suffix tree in constant time

2:36 um and i also promised that we spent linear time for pre-processing so you can kind of figure out from the slider question what you would have wanted to answer there now that all still doesn't sound like rangeman queries right we've had lce and lcp and lca but no rmq

3:04 and that was because at the time we were talking about suffix trees and only later about suffix arrays and with suffix arrays and specifically the lcp arrays this only makes the connection to arrangement queries

3:26 so we call this the enhanced suffix array the suffix array plus the lcp array so here's the two things from back then just to remind um we have both the the suffix array the leaf array giving the indices of the leaves in alphabetical order so these are the starting positions that are stored there but they're stored in lexicographic order okay which is what you get if you draw the suffix tree and then read the leaf indices off left to right you remember those pictures good good i hope so we had the opposite which is the rank array the inverse suffix array that told you if you want to find the suffix that starts at position two in the text where would you find that in the suffix array so you would use the rank array at position two and that tells you the suffix starting there is the ninth in sorted order so you can jump down ninth and then you find it here that was step one so we had suffix array and inverse suffix array to move back and forth between text order and sorted order

4:42 and then we add it to the [Music] suffix array we added the longest common prefix array so for any two adjacent suffixes adjacent in the lexicographic order we stored how long is the longest common prefix so here is this array the red one between those two there's no overlap so it's a zero between these two it's just a so it's a one and between these two it's a word of length three so the lcp entry is a three okay it's been it's been a month or so so i thought it's good to recap that a bit if you take these two things together then you can puzzle together this equation for longest common extensions so we start with

5:39 my favorite picture i guess are text to positions i and j and we'd like to know the longest common extension of those positions we know that this is the longest common prefix of two suffixes namely the suffixes starting at position i and j in the text um shall we make this concrete instead of an abstract example then you can follow the numbers through i think this is more helpful

6:26 don't forget the dollar ah let's pick a somewhat interesting one right um let's pick one and position three because they have some some non-trivial overlap so we want to know the lce of one and three

6:58 now the first step is to translate that to longest common prefix of the two suffixes all right so we know that somewhere here we can figure out the longest common prefix but remember the lcp array only stores this prefix for two adjacent suffixes in sorted order and one and three [Music] happen to be adjacent is that too boring an example should we do one and seven instead

7:47 so i is 1 j7 we can find those here manually they're not adjacent in the lexicographic order so there's no lcp entry that stores their value but if we zoom more into this of course we can take a look at these and we find

8:10 that if these two have something of length two in common and these two have something of length three in common the top and bottom row have something of length two in common it's just this the shortest shared prefix that you find if you walk from the top to the bottom one the shortest that is carried through all the time that's the longest common prefix of of seven and one

8:41 so it should be two here and you might see a connection to range minimum queries now because we we're looking at this lcp array from this position to this position and we're trying to find the minimum in that range the minimum is the shortest thing that is equal between adjacent things and if there's a minimum of two then the first two characters have to be equal between any two pairs and that means they're also equal from the first towards the second and any longer prefix wouldn't be equal because there's some some adjacent pair where they don't match up okay so that's the connection between these two problems

9:30 because we don't have an lcp array entry for every pair of leaves we use the arrangement query on the lcp array to get that value even if it's not explicitly stored and the rest is puzzling together the right indices in in my example here i just said let's try to find the leaves seven and one in the leaf array you don't want to spend the linear search doing that and you don't have to instead you know where they start so you know one and seven so you go to one and seven in the position of the text you use the rank array to find where in the sorted order they are and so that gives you at position two and four you find your two your two suffixes that you're looking for

10:26 that's why we take here the rank array of i and the rank array of j and insert that and notice that also in this example even though i was smaller than j it could happen that r of i is is smaller than r of j that's why in this formula buff you need the minimum and maximum

10:57 good i think that was the most intricate part for this this connection is is a little following five different connections so it's a little a little um needs a little caffeine to follow through the good thing is for now for the rest of this unit you can forget about this connection if you want we'll worry about how to find this arrangement query efficiently and that doesn't rely on this connection but this is one of the prime applications of arrangement queries and because you've seen exactly that i definitely wanted to make that make that make that connection and explain how it works

11:41 so to formalize or state again what follows from this example because we can compute suffix array inverse suffix array and lcp array in linear time for a string we can use any data structure for the rmq problem if that has preprocessing time p of n and query time q of n we immediately obtain a data structure that has the same time bounds for the longest common extensions um because the the pre-processing time or well maybe i should say formally here plus o n right uh suppose the pre-processing time is smaller than linear we still have to compute uh suffix array and inverse suffix array and lcp array

12:29 so whenever you take some solution for rmq you can plug it in and use it for longest common extensions and you essentially get the same same tradeoff unless your pre-processing was boring