Longest common substring problem suffix array part 2

Key Takeaways

welcome back we're going to finish where we left off in the last video in this video I want to do a full example solving the longest common substring problem with a suffix array for this example we're going to have four strings s1 s2 s3 and s4 I have also selected the value of K to be equal to two meaning that we want a minimum of two strings of our pool of four to share the longest common substring between them I have also provided you with a concatenated text we'll be working with as well as the solution at the bottom of the screen in case you want to pause the video and figure it out for yourself the first step in finding the longest common substring between a set of our four strings is to build the suffix array and the LCP array which I have displayed on the right side and the left side respectively while I will be conducting the longest common substring algorithm notice the variables on the left as they change the window LCP and the window LCS values will track the longest common prefix and the longest common substring values for the current window and the LCS length and the Alsea setter will track the best values so far so let's get started initially our window starts at the top and we want the window to contain two different colors so our rule is to expand downwards when we do not meet this criteria as I expand down the suffix is green so we still only have one color I expand down again and still one more green suffix I expand downwards again and now we arrive at a blue suffix and here we are able to perform a range query for our window however our query isn't fruitful because the window longest common prefix value is zero so there's no longest common substring here when we sass by the window color criteria like we do now we decrease the window size I decrease the window size by one and still nothing interesting and decrease the window size again and this time look what we found the current window contains a longest common prefix length of two so we obtained the longest common substring BC and add it to our solution set now we keep shrinking the interval size because we meet the color requirement our window size is now too small because K is 2 so we need two different color strings so we expand once more now something interesting has happened because we find an LC p value of 3 which is larger than our current best value so we update the solution set to have the string and BCD instead of just BC which is one character longer now get to shrink the window size the window was now too small so we expand the LC p value of 0 here so that is no good so shrink the window size now expand to meet the color requirement we get an LC p value of 1 but that doesn't beat our current best which is 3 so shrink the window now we need to meet a color requirement so expand we have only blue string so we keep expanding an LC p value of 1 for this window range so that's no good so shrink now we have an LC p value of 2 we're getting closer to our best but still not good enough so we have to shrink and like let go now expand now something interesting is going on here we have a window LCP value of 3 which is equal to our best so far so instead of saying that the CDE our newfound longest common substring value beats BCD which is of the same length we keep both in the solution set alright so now let's shrink our window interval because we meet the color requirement now expand it we still need one more color expand again our LCP window value is zero so shrink and shrink again now expand LCP value of 1 here that's not good enough so smaller expand i'll see p value of 2 okay we might be getting closer but we meet color requirement so shrink now expand to meet the color requirement these two strings have an Elsa p value is 0 shrink now expand now shrink now we've reached the end and found our solution to the longest common substring problem with 4 strings and a k value of 2 as I was doing the window expanding and shrinking I want you to notice that each time the window either expanded or shrank I only ever moved one of the endpoints downwards and they were always going downwards so we know that the number of windows has to be linear in proportion to the number of suffixes that we have and the number of suffixes that we have is the length of our text T so we come to the conclusion that there must be a linear amount of windows that we must consider which is really good because we want our time complexity be quick so that's for now thank you for watching I hope you learned something and I will catch you next time