Video 6-4: §6.4 Longest common extensions

0:00 Introduction

0:02 in the previous subsection we've saw we've seen some immediate applications of suffix trees to solve various strange problems it turns out for various other problems you need a little extra information the suffix tree alone is not quite enough to solve these and uh what we need in addition are these longest common extensions the suffix trees are a key step to efficiently answer such queries so it will it will build and use on sub it will build on suffix trees and use these as before but a little additional step can boost their power substantially

0:40 Longest common extensions

0:42 so what what are these longest common extensions it's a a problem of independent interest but we'll see more specific use cases a bit it's it's the following problem you're given a string as always in the last couple of units right uh and we want to answer these lce queries longest common extension queries so what are these queries here you're given two positions in the text so as always i like to draw these pictures to make things a little more graphical you're looking at two positions in the text and now you'd like to know how far can you jointly scan to the right where you see the same string okay so formally lce of two positions i and j is uh the longest extension it's the maximal l so that the length l substring starting at i and starting at j of t are equal okay but imagine you have you have two pointers that look at these positions i and j and you ask how long can you move them to the right in lockstep before you find different characters that's the longest common extension problem it turns out the information we need to solve this problem is already contained in the suffix tree clearly any two positions in t correspond to a suffix starting at this position so the longest

2:02 Longest common prefix

2:18 common extension of i and j and t is nothing but the longest common prefix of two suffixes namely the suffix starting at i and j again if you look at this picture if you start at i and j if you take the suffix starting here and the second suffix starting here well clearly the longest common prefix the longest prefix that these two suffixes both have in common that's nothing different than this longest common extension it's just a different way of asking for it

2:58 maybe formally we should say the length of this thing the longest common extension really is is an integer it's the length of this uh extension and um well maybe depends on who defines it um here i defined it as the length sometimes people also use the actual string uh let's leave it at that as as that so the the confusion i'm i'm mentioning is both longest common prefix and longest common extension can either be the length of these um shared strings or it can be the string itself depending on the application one or the other is more convenient to use but it's really the same thing if you have the length you know where it starts in the string so it's just this the substring starting at that position

3:52 so we already know what this is it's the same thing just a different name for the longest common prefix of two suffixes and that again was remember we used this before when we were talking about the longest repeated substring that is the string depth of the longest common ancestor of inj i mentioned the term at the time already so if if you remember the example there was we had um ban aban

4:22 and we had uh an and we were asking for the longest common substring of these two and we found that this was just the a and the reason is that we would walk a band to this leaf and a an to this leaf and the longest the lowest common ancestor of these two leaves is is this node that's the last node they have in common when we walk the root to leave path so um in short and this is really uh highlighted here because you should remember this um i'll we'll review it after easter but we'll use this later on the longest common extension of two positions as we've just argued lengthily is nothing but the longest common prefix of these two suffixes and that is the string depth of the lowest common ancestor of those two leaves with the given indices so you see in all in all of these uh three terms the numbers i and j are involved either it's the starting positions in the text or it's the starting positions often an index of an of a suffix so it's the the name of a suffix if you like or it's the name of a leaf but it's really the same same numbers in all cases so i do remember this one

5:56 we'll come back to it after the christmas break how can we answer these lce queries we could do simple things we could start at the leaves and walk up the tree until we find a common node that is possible but it can be slow in in the worst case you have to walk through the entire tree and there's no uh no no bound on the height of a suffix tree uh better than the near the other or the other option would be um we pre-compute all the possible lcas all ce's longest common extensions or lowest common ancestors we can pre-compute all the lowest common ancestors in a big table but that table is very big so even just writing it out to memory would take quadratic time and that again is not interesting for the problems we have we can't afford this again an amazing result is that you can compute a data structure in linear time in space and then after that computes the lowest common ancestors of any two leaves in constant time it's just blink of your eye and you get the answer this one is a little tricky to understand but if we have time at the end of the module i want to be i want to introduce you to

7:17 how to do this um even though it will not be part of the exam material again a clearly a theoretical breakthrough but also useful in practice because there are implementations that do this very efficiently uh and so this is uh this has again been together with suffix trees these two things are game changers in in stringology

7:42 for now we'll treat the construction of these of this data structure for lowest common ancestors as a black box so um you you may remember this after linear time pre-processing we can compute the suffix tree and the longest the lowest common ancestors in the suffix tree and that together gives us the longest common extensions in a string in constant time after the pre-processing

8:11 Approximate matching problem

8:14 and uh this is something you can use for uh even more interesting problems like this one um that's the approximate matching problem remember so far we were given a text and we were looking for exact matches of our pattern in the text often this is a little too strict especially if humans type the patterns so here we're given a text and a pattern and additionally a parameter a number k and we're now interested in a match well the first match again where uh the part of the text and the pattern don't have to be exactly the same but they have to be within hamming distance of k and so hamming distance that's just counting the number of mismatched characters

9:07 the number of positions where the characters are are different okay if there's no such match uh no such position where we can find something within having distance k then we report no match otherwise we report the first occurrence so in a sense it's it's like searching with typos you can uh substitute one letter for another and it will still find find the occurrences in the text okay

9:37 what we'll do here is we do a similar trick as for the generalized suffix tree uh we take the text and the pattern and make a single string out of it but we separate it with dollars so that we know when when these things end and now we construct the longest common extensions on this combined string um and you could basically do this you you build the generalized suffix tree and then compute the lowest common ancestors in the generalized suffix tree so this is um going from one string to several strings is again with similar tricks as we've seen for the generalized suffix tree is again possible here so we can use longest common extensions also in different strings and it works in essentially the same way