Video 9-2: §9.2 LCE using RMQ

0:02 in the next subsection i want to motivate why we study this problem and maybe that also triggers some thoughts for you uh how efficient we want to solve rmq uh instances uh so here the this is obviously the new abbreviation arrangement queries you might remember what these are i won't mention the last uh these are the longest common prefixes that is uh unit six calling and uh you might also remember the longest common extension problem also unit six and the lowest common ancestor in trees that's something that we also mentioned in unit 6 but only in passing

0:50 so let's uh recap a little bit and i'll just i just copied the slides from back then so if you're a graphically oriented person like myself you profit from seeing the exact same thing the same arrangement so here it is we talked about the longest common extension problem you're given a string my favorite diagram for this was uh like this so you have two positions in a string i and j and you ask what is the the longest

1:24 piece of text that you can read so that it's the same text if you start at i and at j so these two things should be the same and of course because it's longest it means if you go to the next position uh the next position then is not the same otherwise uh your longest common extension would be one bigger

1:53 um well formally the longest common extension was the length of this green part not the string just another nitpick uh to make it a little more convenient and we've already at the time found this this connection there's a an obvious connection between lce and the the suffix tree the longest common extension of two positions is the longest common prefix of two suffixes namely those starting at those positions and in the suffix tree we can find longest common extensions by taking the lowest common ancestor of the leaves for those suffixes and then computing its string depth so our example back then was this uh banana ban

2:40 and so you could for example ask what's the longest extent longest common extension starting here and here that's position 0 1 2 3 4 5. so if you execute this you would find i and j here and here their lowest common ancestor is this node and it has string depth one so that would mean i can read one character that is equal and then the next one is actually already a mismatch and that works out in in our example okay

3:25 that was what we noticed at the time and then we found that this longest common extension problem uh is really useful in doing all sorts of extra clever algorithms on strings using the suffix tree plus this uh lce data structure allowed us to solve some other interesting problems remember the kangaroo algorithm for finding approximate matches

3:55 and at the time i left this uh so this is this is the main point here on the of this slide at that point i told you there is a magic black box for the lca problem finding lowest common ancestors in constant time with linear time pre-processing on the tree and that can solve lca and hence also lce in an arbitrary string by using the suffix tree okay

4:28 uh so that is a reminder of what lc a and lce was the next thing to remember is we also had lcp the longest common prefix and that was when we talked about suffix arrays not suffix trees but arrays suffix

4:53 instead of looking at this lca question we can now look at arrays and so this is nothing we wrote down at the time but let me illustrate that on an example before we move on so again slides from back then remember just for uh getting the notation in everyone's head again we had the suffix array l the leaf array had the leaves of the suffix tree in sorted order that is just the suffixes in sorted l tells you where does this suffix start um the first the second etc in in the sorted order and we also had r the rank array which is um the other direction you have for the the inverse permutation you have the the starting positions in the text and then r tells you what is the rank in the sorted list and so you can use this to go right and left in this picture now um what i'm saying here is suppose we want to find um the longest common extension in banana ban again okay let me

6:25 so let's let's pick the same example uh i take this this position here this a and this a and i want to find from the suffix array from this suffix tree i want to find what's the longest common extension so how much to the left can i walk from this position and get the same string in both in both cases we already know it's just the a but uh suppose we didn't know uh first of all we find this is position one and five in the string so we find positions one and five in the string here that's the leafs a nano band and a band now the going to the right i should have probably started here we know it's position one and five we can use the rank array to tell us where in the sorted list we find this namely position four and one four and one so here we have a band and a nano band

7:35 position one and four in the sorted list that was the rank right this is just oops notice we had this before my tool crashed again let me open it and hope that it can restore the drawing from now

8:11 not clear what uh it didn't like now but um there we are again okay it's only a couple of things that okay one more time where are we i'm trying to find the longest common extension of anaban and abandon or the longest common extension of these positions one and five in this string really i use the rank array to find where in the sorted list i find these two suffixes then when i found them here i can use the lcp array entries

9:16 here those are the lengths of these overlaps between adjacent suffixes in sorted order okay and now the the cool thing is i take this range and find the range minimum query in that the the smallest value in that range

9:45 which is one and one is also the answer we have one character overlap between these two things so this is this is the connection that's spelled out here in big if i want to find the longest common extension between two positions i and j i take r the rank array to map them into this picture on the right where i have them in in the sorted order they might flip positions so 5 becomes 1 and 1 becomes 4 so if even though i was less than j now r of i is bigger than r of j that's why we use min and max to get those two right and now um i take this as a range here in the lcp array and find the minimum in that range and because it's a subarray i can use the range minimum query in the lcp array for that and here you see i i access the ltp array at that index rmq returns the index lcp is the original array so i find just the smallest value in that re in that green range and that is my result okay and the the reason for that is is simply that if this string and this string have anything in common then all of the strings in between have

11:13 anything in common have have the same thing in common and uh we also have to have one place where this value occurs where where this minimal shared prefix exists if all of the values in between were bigger than also the the bot the top and this is abandoned and then a band would share more than one character

11:42 so i know this this slide was dense and uh full of full of somewhat complicated relationships so let's zoom out uh even graphically a bit more uh the reason here why i repeat this in detail is just to motivate why the range minimum query problem occurs here it is effectively another way to solve this longest common extension problem but in the array world not on trees this doesn't need the suffix tree anymore the only thing we need is the inverse suffix array and the lcp array and we've seen in unit 6 already how to compute both in linear time with reasonable algorithms that you you could implement in well say a few days or weeks of uh of concentrated effort um but it's not grace not too crazy and they they are their implementations available in libraries that one can use

12:47 so what does it mean to have rmq for lce we can compute it's basically what i said we can compute the inverse suffix array and the ltp array in linear time so whenever i have a pq solution for arrangement queries that means i have a pq same p and q solution for longest common extensions