Skip to main content


Showing posts from March, 2014

Suffix Trees , a bit complicated but really powerful data structure

Continuing with my obsession with the string matching algorithms , after  KMP algorithm which does string matching in O(n +k) time , where n is length of the string and k is the length of the pattern. I tried exploring another data structure called as “Suffix Trees” , Suffix trees are nothing but compressed tries , where you model all the suffix present in a string in an optimized tree/trie structure. this is how a suffix tree for word “BANANA” will look like some of the other common use cases , where suffix trees can be used is  Find the longest common substring of the strings S and T. This can be done in time O(|S| + |T|) Find the longest substring of S that appears at least m > 1 times. This query can be answered in O(|S|) time. Traverse the suffix tree labeling the branch nodes with the sum of the label lengths from the root and also with the number of information nodes in the subtrie. Traverse the suffix tree visiting branch nodes with information node count >= m. Determine