string problems that occur in text-editing, free-text search, computational biology and other application areas. Primary applications include: String search, in O(m) complexity, where m is the length of the sub-string (but with initial O(n) time required to build the suffix tree for the string) Finding the longest repeated substring Finding the longest common substring Finding the longest palindrome in a string Suffix trees are often used in bioinformatics applications, searching for patterns in DNA or protein sequences (which can be viewed as long strings of characters). The ability to search efficiently with mismatches might be considered their greatest strength. Suffix trees are also used in data compression; they can be used to find repeated data, and can be used for the sorting stage of the Burrows–Wheeler transform. Variants of the LZW compression schemes use suffix trees (LZSS). A suffix tree is also used in suffix tree clustering, a data clustering algorithm used in some search engines. Implementation If each node and edge can be represented in space, the entire tree can be represented in space. The total length of all the strings on all of the edges in the tree is , but each edge can be stored as the position and length of a substring of , giving a total space usage of computer words. The worst-case space usage of a suffix tree is seen with a fibonacci word, giving the full nodes. An important choice when making a suffix tree implementation is the parent-child relationships between nodes. The most common is using linked lists called sibling lists. Each node has a pointer to its first child, and to the next node in the child list it is a part of. Other implementations with efficient running time properties use hash maps, sorted or unsorted arrays (with array doubling), or balanced search trees. We are interested in: The cost of finding the child on a given character. The cost of inserting a child. The cost of enlisting all children of a node (divided by the number of children in the table below). Let be the size of the alphabet. Then you have the following costs: The insertion cost is amortised, and that the costs for hashing are given for perfect hashing. The large amount of information in each edge and node makes the suffix tree very expensive, consuming about 10 to 20 times the memory size of the source text