Editing Suffix tree (section)

== Applications ==
Suffix trees can be used to solve a large number of string problems that occur in text-editing, free-text search, [[computational biology]] and other application areas.<ref name="allisons"/> Primary applications include:<ref name="allisons">{{cite web|url=http://www.allisons.org/ll/AlgDS/Tree/Suffix/|title=Suffix Trees|last=Allison|first=L.|access-date=2008-10-14|url-status=live|archive-url=https://web.archive.org/web/20081013124759/http://allisons.org/ll/AlgDS/Tree/Suffix/|archive-date=2008-10-13}}</ref>
* [[String search#Index methods|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.<ref>First introduced by {{harvtxt|Zamir|Etzioni|1998}}.</ref>