Suffix array finding unique substrings

Key Takeaways

in this video I want to discuss a neat application of suffix arrays and LCP arrays and that is finding and counting unique sub strings there are a variety of interesting problems in computer science especially bioinformatics that require you to find all the unique substrings of a string the naive algorithm has a terrible time complexity of N squared which requires a lot of space the idea is to generate all the sub strings of the string and dump them inside a set a superior approach is to use the information stored inside the LC pra this provides not only a quick but also a space efficient solution I'm not saying that this is the canonical way of finding all unique sub strings because there exists other notable algorithms such as rabbin carp in combination with bloom filters let's now look at an example of how to find unique sub strings let's now look at an example of how to find all the uni substrings of the string a Z a Z a for every string there are exactly n times n plus 1 over 2 sub strings the proof of this I will leave as an exercise so listener but it's really not that hard to derive now notice that all the sub strings here there are a few duplicate ones I have highlighted the repeated sub strings there are exactly 6 of them and 9 unique ones now let's use the information inside the LCP array to figure out which of those sub strings really were the duplicate once in the table on the right I generated the LCP array for the string a a za za remember what the LCP array represents it represents that two adjacent suffixes of the original string shares certain Americ ters with each other so if the LCP value at a search index is say five and there are five characters in common between those two suffixes in other words there are five repeated sub strings between those two suffixes since they come from the same larger string so if we inspect the first LCP position at index one we see that has a value of one we know that the repeated string is the first character in a so we know that a is a repeated substring the next LCP value is three so there are three repeated substring between a z ay and a Z a Z a namely a AZ and ay z a the next interesting LCP values - for the last two suffixes so there are two repeated substrings here we can eliminate z and z a we can then come up with an interesting way of counting all unique substrings we know how many sub strings there are and that is n times n plus 1 over 2 and we also know the number of duplicate strings that is the sum of all the LCP values if this doesn't make immediate sense try out a few examples and play around with it if we go back to the example we just did with the string a Z a Z a and we set N equal to 5 which is the length of the string then we can get the correct answer of 9 by punching N equals 5 and then removing all the repeated substring values summed up in the LCP array alright so if you're looking for a programming challenge concerning counting substrings like I mentioned here you have the link to the cat is online judge for some practice I also included some source code for the suffix array and LCP are a available on github I get dot-com / William Fiza / - structures thank you for watching and in the next video we'll be talking about other applications of suffix arrays and LCP arrays stay tuned