Video 9-2: §9.2 LCE using RMQ

0:00 <Untitled Chapter 1>

0:03 in The Next Step section I want to talk about why this rmq problem is interesting and uh well by chance it just happens to be that there's too many abbreviations with three letters uh or maybe too many long names that need to be abbreviated to be convenient we should recall unit 6 for making sense of that motivation and at that time unit 6 was all about suffix trees and suffix arrays and we talked about the the string problem of longest common extensions so just to refresh memories um we had a single string in the easy version and two positions in that string and I probably Drew pretty much the same picture back then we have two positions I and J and then we ask how many positions starting at these two can I move to the right and see the same string so I want that these two green parts are the same and then the next the next position they differ and then the longest common extension was the length of this green part

0:16 Recall Unit 6

1:23 all right it's all formally defined on the slide so um and we've touched on that last uh when we discussed it in unit 6. the connection at the time where we needed this was to jump around in the suffix tree uh we have exploited that there's the connection to the lowest common ancestors so from the longest coming extension you can go to the lowest common ancestor of two Leafs in the suffix tree and so these two things turned out to be related um by taking the string depth of that lowest common ancestor remember memory is coming back

2:05 and then at the time I left you with this unsatisfying black box where I just told you you have to believe me now and then we went on and now it's time to crack that open

2:21 so I want to give you at the end of the session the full answer to this but let's work work our way there the important bit from back then was um for the longest common extension problem we needed

2:40 this uh lowest common answers during the suffix tree but we also observed at the time already that this is really just um the longest common prefix of two suffixes so that was just them by definition a different name for these things and then at the time we didn't have that but later in unit 6 we talked about suffix arrays and about the LCP array the longest common prefix array which is very very close to this except that the longest common prefix array wasn't defined for all pairs of suffixes instead it was defined if you remember I may be a bit small so you listed all the suffixes of a text in alphabetic order and then for two adjacent ones the LCP array gave you the length of the longest common prefix but the um the essential information is still in there and the relation is this so the longest common extension of these two um maybe my infamous picture again we have positions I and J now we ask how much do they um they coincide at the beginning so we can draw them on top of each other that's the suffix starting at I that's the suffix starting at J and we ask how many positions can I um find there where they are equal before

4:14 they differ so that's the longest common longest common prefix query but between arbitrary suffixes we don't necessarily have them nicely adjacent but if you look at this uh alphabetically sorted list you notice it's it's not really that far away

4:42 let me try to pick um an example illustrating that Maybe let's take the this suffix and this suffix so they are not adjacent in order so we don't have an LCP entry showing us what the longest common prefix is but we can still Trace so these have one thing in common these have two things in common these are three things in common but we already know these first two they differ on the second position so that's like um a low Watermark it cannot get better than that and the same for the others it's great that they differ on more but really we need the the lowest the lowest common thing determines what this and this suffix have in common so it's exactly a range minimum query on the LCP array and again the reason the reason for that is uh we want the strings to be the same all along so these two different on the fourth position the first three are the same that also means this and this they um share the first two characters but then differ on the third is always the smaller of the two that wins and so if you take two arbitrary positions it's exactly the range minimum that you uh that you have as LCP now the

6:10 range minimum value not the position but you can read that out from the LCP array and that's what this formula up here says let me try to get all of that on the picture the longest common extension between two suffixes starting at two positions is whatever the LCP array contains at a certain position and what's the position it's the range minimum query answer on this array and now I I have to order them because um the the suffix array this or the inverse suffix array the r array that brings us from the left to the right it might reverse I and J if I go from left to right they might cross so I have to take the smaller and the bigger of the two that's why the formula looks a bit a bit messy but it's it's not actually more complicated it's really taking the two suffixes finding where they are in sorted order that's what R does and then taking the range minimum in the LCP array on that on that position that's the connection I know it's a few hops um

7:25 Finally: Longest common extensions

7:27 so maybe you have to pick some arbitrary two strings and do an example just follow along what the formula does the full example is is on the slide so in a way all the information is is there that you need and maybe that makes it clear so that's the motivation that's one motivation for the range minimum query problem uh it turns out there there are other situations where again in Disguise you have the same problem you have some some fixed array and you want to find Minima of in a certain range

8:18 the connection quantitative in terms of the um the performance uh we should well first of all we can compute all the ingredients that we have here so what do we need we need the inverse suffix array for that we probably want first the suffix array and then the inverse suffix array and we need the LCP array and then we can start with range minimum queries we can compute both of these ingredients so all three ingredients in linear time that's things we discussed in in line at length in unit 6. and so I well I guess uh the other thing any any pre-processing

8:41 RMQ Implications for LCE

9:09 maybe we should put um let me fix the slides here I mean this is clearer that way well the next sentence is about to say you have some solution for the range mean query problem and you can pluck that in by the formula on the previous slide to solve the longest common extension problem how good is the solution you get for from that and so what this says is suppose you have an rmq solution with pre-processing time p and query time Q then we get a solution for the longest common extension problem that needs the same pre-processing time plus Big O of n for computing the arrays and we inherit the same query time because we don't actually do anything at the query time other than table lookup looking at the position in an array

10:11 the problem is of the Black Box in unit 6 was that we can do this in linear pre-processing time and constant query time okay that's where that's what we're trying to do and especially the second looks quite challenging and in a way also the first that's the time you just need to read the array if you do any any substantial pre-processing I guess you need to read at least the array you're given but the claim is that's all you need is proportional to the time to read the array once and then queries are constant time it doesn't depend how big the array is