Notes on Suffix tree

# From wiki <http://en.wikipedia.org/wiki/Suffix_tree>

# A good explanation : <http://marknelson.us/1996/08/01/suffix-trees/>

# A very nice tutorial on Suffix tree <http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm> 

Have You Seen This String? 

The Suffix Tree 

Let's Find That Substring 

Other Nifty Things You Can Do with a Suffix Tree 

How to Build Your Very Own Suffix Tree 

Exercises 

References and Selected Readings 

[Applications]

> longest repeated substring problem:

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

The longest repeated substring problem is finding the longest substring of a string that occurs at least twice. This problem can be solved in linear time and space by building a suffix tree for the string, and finding the deepest internal node in the tree. The string spelled by the edges from the root to such a node is a longest repeated substring. The problem of finding the longest substring with at least k occurrences can be found by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least k descendants.

Solutions from Sartaj Sahni

Find the longest substring of S that appears at least m > 1 times. This query can be answered in O(|S|) time in the following way:
(a) 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.
(b) Traverse the suffix tree visiting branch nodes with information node count >= m. Determine the visited branch node with longest label length.

Note that step (a) needs to be done only once. Following this, we can do step (b) for as many values of m as is desired. Also, note that when m = 2 we can avoid determining the number of information nodes in subtries. In a compressed trie, every subtrie rooted at a branch node has at least two information nodes in it.

[Some Notes]

An example of Surfix Tree:

<http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm#search>

 
Figure 4 A more humane drawing of a suffix tree

A fundamental observation used when searching for a pattern P in a string S is that P appears in S (i.e., P is a substring of S) iff P is a prefix of some suffix of S. 

Let's take the above figure as an example, 

if follow A->C->H : pe is the prefix of eper

[Some Related Codes]

• Suffix Trees by Dr. Sartaj Sahni (CISE Department Chair at University of Florida)
• Suffix Trees by Lloyd Allison
• NIST's Dictionary of Algorithms and Data Structures: Suffix Tree
• suffix_tree ANSI C implementation of a Suffix Tree
• libstree, a generic suffix tree library written in C
• Tree::Suffix, a Perl binding to libstree
• Strmat a faster generic suffix tree library written in C (uses arrays instead of linked lists)
• SuffixTree a Python binding to Strmat

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥