Video 6-9: §6.7 LCP arrays

0:00 <Untitled Chapter 1>

0:02 in the next step section i want to talk about the lcp array the longest common prefix array that will be an addition to the suffix array that allows us to solve many more of the problems that we could attack with the suffix tree but now using just the suffix array so what is the lcp array

0:19 What Is the Lcp Array

0:30 to get you a little bit back awake and in shape let's think about one of the applications namely the length of the longest repeated substring that was remember that was the single string version of the problem that knuth conjectured would not be possible to solve in linear time and it also was uh the first problem where we've seen that suffix trees can do this easily now i'm asking you what exactly was the feature of suffix trees that we used for this

1:07 i think all of these features that are listed here are actual features of suffix trees so suffix trees can do all of these and there's algorithms that make use of that but specifically for this problem to find the longest repeated substring there's there's really one of them that is very important

1:30 for finding the longest repeated substring without that feature you don't get anywhere close the actual algorithm might implicitly rely on some of the others so it's probably hard to say that any of these is completely irrelevant

1:54 but there's there's definitely one feature that i would say is is the key feature for this problem okay let's see what we have um i love to get the the usual 25 people voting so maybe we can spend them another minute on this but i do want to move on also to show you the construction algorithm of this so maybe let's um show the results here now also because most of the people got the most important thing right so i marked the other answers as not correct but the truth is that um the algorithm probably uses some of the others as well the traversal probably needs the constant time traversal to child or parent nodes um we don't really use the order of leaves to be fair to be honest we don't really use the jumping to the leftmost leaf in in the subtree but the the key thing is that we know the string depth of internal nodes because remember every internal node is something shared between at least two suffixes shared between between at least two suffixes means it's a repeated substring the path to that node and the string depth is the length of that string on the path from the root to that node so that is precisely what we need

2:16 Construction Algorithm

3:20 for finding repeated substrings and then the maximal string depth of any internal node is the longest repeated substring right so that's that's that was that how can we possibly add this back to the suffix array internal nodes is inherently something in the tree structure of the suffix tree and that is completely lost by simply looking at the order of leaves right i even said the order of leaves is exactly something in the suffix tree that we did not use for this problem so how can we how can we add this back remember the algorithm for finding the longest repeated substring was like this we compute the string depth of all nodes and then we find one node one internal node with maximal string depth so again let's briefly do this here string depth one two three three one two so the maximal ones are these two and uh here you see there's two maximal repeated substrings in banana band it's ban occurring ban ban here and there and anna which occurs here and here in an overlapping way but that's in general okay for repeated substrings it seems unclear how to do this in a suffix array by itself but if we add another piece of information we can actually do it and that is the lcp array which is

4:02 Longest Repeated Substring

4:51 Lcp Array

4:54 an array of numbers again so that's similar to the suffix array and that's similarly as before an advantage for implementing it it doesn't have an entry for zero that's just a technicality i want to point out usually i let all our arrays start at zero as this convention in most programming languages but for the lcp array it's convenient not to do this the arth entry in the lcp array is the longest the length of the longest common prefix of two suffixes namely two that are neighboring in the sorted order or neighboring leaves in the suffix tree namely those that start at position r and uh whatever is uh the uh the next one so the the r suffix in sorted array in the sorted order and the the previous one that explains why there's no entry for zero because there's no previous entry for zero so um

5:57 yeah let me um okay we'll see the example of the next slide in full detail so maybe that's that's enough i just want to point out that between any two neighboring leaves so these are remember left to right the leaves this gives you the suffix array if you just walk around the tree in this in this manner the specifics array of this of the string and a band will be 9573 blah blah blah blah blah

6:30 that's what we used before now between any two we will have this lcp array so the lcp array will correspond to the point between it will always be something between two two adjacent

6:51 leaves and if we take for example the seven and the three this point corresponds to this note the lowest common ancestor of these two leaves and you'll see the lcp array stores essentially the string depth of this node that's the connection to string depths and to finding longest repeated substrings but we'll go over the example in full detail here

7:19 let's make the the full connection here's the suffix array and it will be the same example so remember i promised it's 9 5 7 3 1 etc 9 5 95731 etc so that matches up that's the the suffix array these are the suffixes in sorted order we can find the longest common prefix between those so i read that i wrote that in between these overlap in terms of a these have a n in common these have ana in common etc so these are exactly the labels of paths to internal nodes that's no coincidence every internal node in a tree is the lowest common ancestor of two adjacent leaves you can think about why that is true but that's that's always the case in the bi in a in a compacted try

8:15 so here we have again the suffixes in sorted order and their lcp values these are the strings and the lcp array stores the length of this shared prefix okay that's all there is to it now um so far

8:35 this is this is just the definition it's very elementary very very simple you can sort all the suffixes then you get the the suffix array you can compare how much do they overlap then you get the lcp array i've already hinted at a connection to suffix trees but you can actually make this very explicit and in a sense these two arrays contain all the information about the suffix tree and that's really cool because that will mean those two together will allow us to compute the suffix tree but we don't really want we don't really have to do that we can actually live with those two uh alone but we'll we'll come back to that let's see how this connection works there's the notion of lcp intervals that is the range of the the suffixes in sorted order that share a common prefix and because they're sorted alphabetically these are always intervals so there's a well a trivial one with the empty string every every string has the empty string as a as a prefix so that's saying nothing but we need a root for our tree and the root corresponds to sharing at least nothing then there's a bunch of strings that start with an a and these are all grouped together these are these four strings that's an

9:22 Lcp Intervals

10:02 lcp interval of 3 because the common the shared prefix is always between these so the length 3 here actually means 4 or suffixes then there's a smaller interval of those that share a n these are these three a n a and a n and there's an even smaller one that share ana ana that's only these these two suffixes then fix can be degenerate as in this case um there's only two that have a start with a b the same two start with ba and actually ban so there's only this interval corresponding to this this entire thing and that that will be an indication that there's um an edge with a longer string label

10:56 so to make that connection complete here's the suffix tree again drawn sideways and you can make a one-to-one connection between the internal nodes of the suffix tree and the lcp intervals and

11:12 these intervals are well nested uh so whenever you have a smaller sub-interval it's completely contained in the parent interval that's exactly as subtree subtrees are contained in the subtree of the parent et cetera so this is a perfect mapping and it means that all the information of the suffix tree is entirely contained in the suffix array and the lcp array okay that's a really cool picture to keep in mind because it means we can entirely at least for implementing it we can entirely do away with the suffix tree and only concentrate on these two arrays which are much easier to uh to store and to handle in code but we effectively have the same information still present okay