Video 8-9: §8.8 The LCP array

0:00 Introduction to LCP array

0:03 in the last section we'll look at the LCP array um which will turn out to be the solution to both applying the suffix array in the same examples we've seen for suffix trees uh and to finally clear this blackbox of how to compute the suffix tree the full one in linear time so far we've only done that for the suffix

0:30 array and uh to motivate that um let me me um remind you or ask you to um remember what we needed for the the first of these more interesting applications which was uh finding the longest repeated substring in a string so again this was find some substring in the text that occurs and in at least two positions it's fine if these are overlapping occurrences uh we could solve that in linear time using suffix or trees and we used some features of the tree there and that will guide us towards what's still missing if we just have the suffix

1:54 there's really just one answer that's definitely yeah I think it fizzled out a bit so um there's been votes for most answers but the the majority is uh is on the right track so uh if you just remember from from yesterday basically uh the key feature that we needed was the string depth of internal nodes we needed the internal nodes uh to iterate through in particular so just as a reminder um the algorithm was was very simple if you have the suffix tree available you compute the string depths of the nodes or you remember that it's actually a compact try and you have the string depths anyways uh and then you find one of the internal nodes of maximal depth maximal string depth and read off the path from the root to that node so in our example we found that those two solutions here the deepest are tied for these two it's either Ben or Anna both is the longest repeated substring it doesn't necessarily have to be unique so if we just have a suffix array it might be not so clear how to do

3:56 that but we can indeed add a second array and then it becomes possible uh that that will be the LCP array the longest common prefix array it's a term that we've had uh already on the slides back then uh it there it stood for taking any two suffixes give me the longest common prefix the longest common part that they share um but it turns out that's you know that's too much if I if I can take every pair of leaves that would be quadratic in size so we don't even have the time to write that down uh but we can strip it off to only look at adjacent leaves in the sorted order so the key definition here is is this one the AR entry in this LCP array is taking the leaf the AR leaf leaf of rank R and leaf of rank R minus one and compute their longest common prefix so in a way um

3:59 Defining the LCP array

5:05 what we have is we have those leaves here in that order that's the leaf array the suffix array right it has uh 9573 and so on in that order if you check with the example from before and the um the LCP

5:26 array as for adjacent pairs in here a number namely the string depth of their longest common so the the string depth of their lowest common ancestor in the tree so here it would be zero here it would be the lowest common anest is this node so it would be one for these two it would be two because that leads to that node where these branch of the lowest common ancestor of those two is this which is three and so on and so so forth here we go back to zero then we have another three here nobody can read that another three maybe I should this this could be mistaken for zeros I guess I'm just trying to show uh what leaves they correspond to uh here we have another zero because the lowest common ancestor is the root here we have one and here we have another two so if I straighten this out the leaf array would be 9 5 7 3 1 6 0 8

6:37 42 that's this um and the the LCP array you should really imagine it's sitting between those numbers so so it should sit here 0 1 2 3 03 0 1

7:14 2 unfortunately we can't really tell most programming languages that we want this to have index 1.5 and this index one one. 0.5 and 1.5 and so on uh so instead it's shifted so this is this is index one two three and so on so it starts with one here unlike most of our arrays we don't use the Zero Entry for this

7:43 one so that is LCP okay that's from this example that's what you should uh what you should imagine here now for the longest common substring problem all we need to do is find the largest entry in the LCP array and we find indeed there's 2 * the three so that's the length of the longest common of the longest repeated substring if you want to know what string that is we have to check at what indices that occurs and that gives us the two um the two suffixes that start with that

8:25 thing so here's that um connection drawn a bit nicer again that's the leaf array that's the suffixes that it corresponds to here are the longest shared prefixes the longest common prefix between any adjacent two uh suffixes nothing for these two because they differ on the first uh character already and for some others there's a a longer common prefix up to three characters here that's why the uh LCP array looks like

8:59 LCP intervals and tree logic

9:01 this now you can draw the same information slightly differently as as intervals uh because it turns out the the things that are shared so it's not just these numbers go up and down also if you look at the the part that is shared a a an A and A they all share an a at the beginning so you can say there's a an interval among the sorted list of suffixes where they all start with an A and nested within that interval is one where they all start with a N and so on and so forth sometimes these are just a single uh a single pair of suffixes sometimes there are

9:43 more and here comes the cool trick so that's the the part to pay attention to uh these LCP intervals correspond one to one to the nodes of a suffix tree so again if I have the suffix tree every internal node corresponds to to such an LCP interval so a range in the sorted list of suffixes and a prefix that everything in that range shares uh the root corresponds to this dummy shared prefix of the empty string that everyone starts with nothing okay fine that's kind of a a corner case so that everything is covered by one interval then the children of the root um there's one that goes to a that's this range that's the LCP interval where everything starts with an A and this holds through in the other direction um there's nothing that uh only starts with B the whole thing is contained so everything that has that starts with the B actually starts with B an that's why there's an internal note for for the prefix B but nothing in between there's no no other internal nodes before that so it's really a a onetoone correspondence and that might help you uh appreciate that from just the LCP array and the suffix array you can reconstruct everything that's in the tree all the information is is in there

11:17 uh it might be a little bit hidden or it might be a little um opaque to see it um but the key information is there and so you can indeed reconstruct the tree with a simple algorithm from those two

11:37 arrays uh we don't do the full code but you'll do an example in in the tutorials to practice it a bit uh in a way you can you can do it like this you align the suffixes in sorted order and if you have if you have the longest common prefixes it's easy to also determine these intervals um it's just ranges where there's the same same uh minimal number so this this a corresponds to a range where the LCP does not drop below one but there is one occurrence of that number and from that you can you can reconstruct the suffix

12:19 tree uh what I want to show you here as the last bit is where does this LCP array come from I've introduced yet another array so we need an algorithm to compute it and again it should be in linear time to be

12:20 Efficient LCP construction

12:35 interesting so the last section will be about constructing the LCP array efficiently you can go by the definition and compute it naively uh often that's not very slow but in the worst case it takes linear time for each entry so quadratic overall again a possible worst case is the degenerate text of all A's uh where you have these long shared suffixes all the time the insight to speed that up is if you have if you if you imagine doing this naive algorithm for every pair next pair of leaves you uh start comparing from the beginning uh how many characters are there the same suppose you do that and you have one really long entry for example here um you have this uh valid grammatically correct English sentence of buffalo buffalo buffalo buffalo and you can add more Buffalo to this if you haven't seen there's a fun one but it's a bit beside my point uh if that's your text then you may have um these two suffixes in sorted order that share a long long shared prefix uh whenever you have this we actually are guaranteed to find more large values and uh we can kind of deduce those let me show that on an example and then we'll do the proper algorithm so suppose you have a first

14:03 few of these um of suffixes of this text in sorted order and you found um a really long Common prefix between those two well if I take off the first character of those two then they become to other suffixes but they still share a lot because it's just one character less if they were the same for the first 18 characters then chopping off that first character means they share uh 19 characters they still share 18 the tricky bit is just uh to find where does that 18 go we know there's two suffixes that have the longest common prefix of 18 but which ones um and what's more it it may not be that these are adjacent and then they don't actually have an entry there might not be an at in anywhere in the LCP array because these two are not adjacent in sorted order that's the slight caveat but otherwise this is the key idea if you have one long longest common prefix between two suffixes then there must be many other shorter suffixes that all lead up to this long shared prefix and so you can capitalize on that and amortise the cost

15:36 and that's what uh casay Al's algorithm does um the trick is to compute the LCP entries the values in the LCP array in a smart order and it turns out the smart order is not going from beginning to the end of the LCP array but to process the suffixes in the order of their length so let me illustrate how this this works on an example and then um we'll we'll see the the full code afterwards uh so we start with the longest possible suffix the entire text now we find where does this lie in the sorted order of suffixes so we use our right to the right array the rank array to know the rank of this is six so I find it at position six in the sorted list if I know that I can go to position five the previous one that's this one and I can check how many characters do they share now this I do naively so I go through the characters one after the other they share these they share this but then it's done right then uh the shared prefix stops so I determined one entry uh one shared one longest common prefix entry namely three at position six okay now we're trying to make use of that

17:01 information and the way we do that is if we now go to the next suffix in the text order the one that just loses the B I'll try to find again where does this occur in the sorted list I use my rank array so I go to four and I find the one that's before that in sorted order and here comes the trick because there there were three shared letters earlier if I just use uh just remove this one B at the beginning I have two matches two characters that definitely are the same without checking so I don't need to compare those two again these are for free and I start comparing one character after that in this case there's one more character but then uh the twoo strings differ so I have another entry of three uh but I only paid one comparison to get it the other two were for free and that's all that it keeps going like this uh that's the algorithm so if we go to the next position um we uh check where do I find that in the sorted order well it's at position nine so we jump down here now we look at these two strings and we know they had a length three shared prefix before if I

18:20 lose the first character there's definitely two that are shared and in this case that's also where it stops the next character differs so I have an entry two to go in into my LCP array and I paid a single comparison

18:39 again and we keep going the same way in each case we take the entry that we wrote Into the LCP array last time subtract one because we removed one character and those that's the number of characters we definitely have a match for and the others we just naively check for this one we go over here we know one character is inherited one match uh there's actually one more that we pay for and then we get an entry of two go to the next one find where it is we have one inherited match that's the only one so we leave it at that so for the next example here we don't have any inherited matches because 1 minus one is zero and here indeed the first character already differs so we get a zero and the same thing happens here again

19:30 and uh then for this one uh we don't have any inherited matches but we find by comparing that there's one character that all if you write that down as an algorithm uh it looks like this uh we need the suffix array and the inverse suffix array to be computed already we need that to go back and forth between those between those two um left and right pictures we need the rank array to go from a suffix here to its location in the sorted list but then we also need the the suffix array to go from position seven position six where does that guy start I need to know where I have to compare so I need both L and R these are computed up front and we know how to do that from the sections before from today L remembers my uh my match that I found so far and then I go through all the suffixes in text order I look where it is on the right hand side that's my two the right array um I take uh the suffix above me

20:45 and find where that is in where where that starts in the text and then I do my naive check but I start with these L matches that I inherited so those I don't check I start at i+ L and IUS one plus L and keep increasing that as long as there's a match then I store my um the longest the prefix I found in the LCP array and then uh for the next round I remember I remove one character so L gets one smaller for the next round it's fairly short code it does exactly what I've shown you in the example um it's just a little getting all the indices in your head is a bit confusing I always um prefer the example and then derive the code from

21:26 Algorithm analysis and usage

21:43 that uh let's briefly analyze um that algorithm uh because they skipped the fire alarm last week I think I was hoping they might also delay it but no there we are okay let's let's quickly analyze the algorithm uh because in a way it looks dangerous it has this Inner Loop and it has an outer loop so can we guarantee that it doesn't go quadratic um and the reason again uh similar to some string matching algorithms we've seen is we can do an amortised analysis uh we can separately count how often this um comparison comes out as equal or as not equal the not equals are easy because whenever I have a not equal I skip this inner loop so I can only have one uh one mismatch for each outer loop iteration so there's at most n such comparisons where the outcome is not equal and for all the ones where I have the equal outcome I increment L

23:02 afterwards but L is never bigger than n and we always make it one smaller so it's uh only make it one smaller at most and so if I add this up um I have at most two n comparisons that I spent where the outcome is equal it's similar to uh to KMP and some of these algorithms um it's kind of a a potential or a bank account argument uh we keep L from the round and we only adjust it slightly so it can move up and down uh but if it moves up a lot then we profit from that for many future durations where we can't have another expensive operation if one iteration of the outer loop made L move very far and spend a lot of time in this inner loop then the next iteration cannot do the same okay so overall again it's linear timee because all the um key operations only happen um a linear number of

24:11 times uh with this we can puzzle together our algorithm for suffix trees again the details um you will you will try in the in the tutorial you compute the suffix array and then the LCP array and you use this connection with LCP intervals to know exactly which internal nodes there are and so you can reconstruct the tree from

24:37 that these two things uh suffix array plus LCP array uh is also called the enhanced suffix array because the suffix array has been enhanced by the LCP array um but uh this really is um a more General thing uh it's it's a bit more tricky to reason about as compared to having the suffix tree explicitly uh but it turn turns out you can you can simulate everything that you can do in the suffix tree you can simulate based on these two arrays um with uh with maybe extra tricks but uh uh it's essentially just your mental load is higher in designing the algorithms uh but there's an almost automatic translation if you tell if you tell me how to do it on a suffix tree you can translate how to do it using just the two arrays uh the much less space they don't have a dependence on the alphabet in the sense that the suffix tree had and we've seen to algorithms today to compute both arrays in linear time and they're a bit more tricky than many of the things we've seen but not too