Editing Suffix tree (section)

{{short description|Tree containing all suffixes of a given text}}
[[Image:Suffix tree BANANA.svg|thumb|250px|right|Suffix tree for the text <code>BANANA</code>. Each substring is terminated with special character <code>$</code>. The six paths from the root to the leaves (shown as boxes) correspond to the six suffixes <code>A$</code>, <code>NA$</code>, <code>ANA$</code>, <code>NANA$</code>, <code>ANANA$</code> and <code>BANANA$</code>. The numbers in the leaves give the start position of the corresponding suffix. Suffix links, drawn dashed, are used during construction.]]

In [[computer science]], a '''suffix tree''' (also called '''PAT tree''' or, in an earlier form, '''position tree''') is a compressed [[trie]] containing all the [[suffix (computer science)|suffixes]] of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.

The construction of such a tree for the string <math>S</math> takes time and space linear in the length of <math>S</math>. Once constructed, several operations can be performed quickly, such as locating a [[substring]] in <math>S</math>, locating a substring if a certain number of mistakes are allowed, and locating matches for a [[regular expression]] pattern. Suffix trees also provided one of the first linear-time solutions for the [[longest common substring problem]].{{#tag:ref|[[Donald Knuth|Knuth]] conjectured in 1970 that the problem could not be solved in linear time.<ref>{{cite journal | author1=Donald E. Knuth | author2=James H. Morris | author3=Vaughan R. Pratt | title=Fast Pattern Matching in Strings | journal=SIAM Journal on Computing | volume=6 | number=2 | pages=323&ndash;350 | date=Jun 1977 | doi=10.1137/0206024 | url=https://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Knuth77.pdf }} Here: p.339 bottom.</ref> In 1973, this was refuted by Weiner's suffix-tree algorithm {{harvtxt|Weiner|1973}}.}} These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.