Suffix tree

The concept was first introduced by {{harvtxt|Weiner|1973}}.

Rather than the suffix $S[i..n]$, Weiner stored in his trieThis term is used here to distinguish Weiner's precursor data structures from proper suffix trees as defined above and unconsidered before {{harvtxt|McCreight|1976}}. the prefix identifier for each position, that is, the shortest string starting at $i$ and occurring only once in $S$. His Algorithm D takes an uncompressedi.e., with each branch labelled by a single character trie for $S[k+1..n]$ and extends it into a trie for $S[k..n]$. This way, starting from the trivial trie for $S[n..n]$, a trie for $S[1..n]$ can be built by $n\; -\; 1$ successive calls to Algorithm D; however, the overall run time is $O(n^2)$. Weiner's Algorithm B maintains several auxiliary data structures, to achieve an overall run time linear in the size of the constructed trie. The latter can still be $O(n^2)$ nodes, e.g. for $S\; =\; a^n\; b^n\; a^n\; b^n\; \backslash \$\; .$ Weiner's Algorithm C finally uses compressed tries to achieve linear overall storage size and run time.See :File:WeinerB aaaabbbbaaaabbbb.gif and :File:WeinerC aaaabbbbaaaabbbb.gif for an uncompressed example tree and its compressed correspondant.

Donald Knuth subsequently characterized the latter as "Algorithm of the Year 1973" according to his student Vaughan Pratt.{{OR|reason=Weiner gave several algorithms; Knuth probably referred to Algorithm C.|date=February 2020}}{{sfnp|Giegerich|Kurtz|1997}}

The text book {{harvtxt|Aho|Hopcroft|Ullman|1974|loc=Sect.9.5}} reproduced Weiner's results in a simplified and more elegant form, introducing the term position tree.

{{harvtxt|McCreight|1976}} was the first to build a (compressed) trie of all suffixes of $S$. Although the suffix starting at $i$ is usually longer than the prefix identifier, their path representations in a compressed trie do not differ in size. On the other hand, McCreight could dispense with most of Weiner's auxiliary data structures; only suffix links remained.

{{harvtxt|Ukkonen|1995}} further simplified the construction.{{sfnp|Giegerich|Kurtz|1997}} He provided the first online-construction of suffix trees, now known as Ukkonen's algorithm, with running time that matched the then fastest algorithms.

These algorithms are all linear-time for a constant-size alphabet, and have worst-case running time of $O(n\backslash log\; n)$ in general.

{{harvtxt|Farach|1997}} gave the first suffix tree construction algorithm that is optimal for all alphabets. In particular, this is the first linear-time algorithm

for strings drawn from an alphabet of integers in a polynomial range. Farach's algorithm has become the basis for new algorithms for constructing both suffix trees and suffix arrays, for example, in external memory, compressed, succinct, etc.

The suffix tree for the string $S$ of length $n$ is defined as a tree such that:{{harvtxt|Gusfield|1999}}, p.90.

1. The tree has exactly n leaves numbered from $1$ to $n$.
2. Except for the root, every internal node has at least two children.
3. Each edge is labelled with a non-empty substring of $S$.
4. No two edges starting out of a node can have string-labels beginning with the same character.
5. The string obtained by concatenating all the string-labels found on the path from the root to leaf $i$ spells out suffix $S[i..n]$, for $i$ from $1$ to $n$.

If a suffix of $S$ is also the prefix of another suffix, such a tree does not exist for the string. For example, in the string abcbc, the suffix bc is also a prefix of the suffix bcbc. In such a case, the path spelling out bc will not end in a leaf, violating the fifth rule. To fix this problem, $S$ is padded with a terminal symbol not seen in the string (usually denoted $). This ensures that no suffix is a prefix of another, and that there will be $n$ leaf nodes, one for each of the $n$ suffixes of $S$.{{harvtxt|Gusfield|1999}}, p.90-91. Since all internal non-root nodes are branching, there can be at most $n-1$ such nodes, and $n+(n-1)+1=2n$ nodes in total ($n$ leaves, $n-1$ internal non-root nodes, 1 root).

Suffix links are a key feature for older linear-time construction algorithms, although most newer algorithms, which are based on Farach's algorithm, dispense with suffix links. In a complete suffix tree, all internal non-root nodes have a suffix link to another internal node. If the path from the root to a node spells the string $\backslash chi\backslash alpha$, where $\backslash chi$ is a single character and $\backslash alpha$ is a string (possibly empty), it has a suffix link to the internal node representing $\backslash alpha$. See for example the suffix link from the node for ANA to the node for NA in the figure above. Suffix links are also used in some algorithms running on the tree.

A generalized suffix tree is a suffix tree made for a set of strings instead of a single string. It represents all suffixes from this set of strings. Each string must be terminated by a different termination symbol.

A suffix tree for a string $S$ of length $n$ can be built in $\backslash Theta(n)$ time, if the letters come from an alphabet of integers in a polynomial range (in particular, this is true for constant-sized alphabets).{{sfnp|Farach|1997}}

For larger alphabets, the running time is dominated by first sorting the letters to bring them into a range of size $O(n)$; in general, this takes $O(n\backslash log\; n)$ time.

The costs below are given under the assumption that the alphabet is constant.

Assume that a suffix tree has been built for the string $S$ of length $n$, or that a generalised suffix tree has been built for the set of strings $D=\backslash \{S\_1,S\_2,\backslash dots,S\_K\backslash \}$ of total length $n=n\_1+n\_2+\backslash cdots+n\_K$.

You can:

• Search for strings:
• Check if a string $P$ of length $m$ is a substring in $O(m)$ time.{{harvtxt|Gusfield|1999}}, p.92.
• Find the first occurrence of the patterns $P\_1,\backslash dots,P\_q$ of total length $m$ as substrings in $O(m)$ time.
• Find all $z$ occurrences of the patterns $P\_1,\backslash dots,P\_q$ of total length $m$ as substrings in $O(m\; +\; z)$ time.{{harvtxt|Gusfield|1999}}, p.123.

• Search for a regular expression P in time expected sublinear in $n$.{{sfnp|Baeza-Yates|Gonnet|1996}}
• Find for each suffix of a pattern $P$, the length of the longest match between a prefix of $P[i\backslash dots\; m]$ and a substring in $D$ in $\backslash Theta(m)$ time.{{harvtxt|Gusfield|1999}}, p.132. This is termed the matching statistics for $P$.
• Find properties of the strings:
• Find the longest common substrings of the string $S\_i$ and $S\_j$ in $\backslash Theta(n\_i\; +\; n\_j)$ time.{{harvtxt|Gusfield|1999}}, p.125.
• Find all maximal pairs, maximal repeats or supermaximal repeats in $\backslash Theta(n\; +\; z)$ time.{{harvtxt|Gusfield|1999}}, p.144.
• Find the Lempel–Ziv decomposition in $\backslash Theta(n)$ time.{{harvtxt|Gusfield|1999}}, p.166.
• Find the longest repeated substrings in $\backslash Theta(n)$ time.
• Find the most frequently occurring substrings of a minimum length in $\backslash Theta(n)$ time.
• Find the shortest strings from $\backslash Sigma$ that do not occur in $D$, in $O(n\; +\; z)$ time, if there are $z$ such strings.
• Find the shortest substrings occurring only once in $\backslash Theta(n)$ time.
• Find, for each $i$, the shortest substrings of $S\_i$ not occurring elsewhere in $D$ in $\backslash Theta(n)$ time.

The suffix tree can be prepared for constant time lowest common ancestor retrieval between nodes in $\backslash Theta(n)$ time.{{harvtxt|Gusfield|1999}}, Chapter 8. One can then also:

• Find the longest common prefix between the suffixes $S\_i[p..n\_i]$ and $S\_j[q..n\_j]$ in $\backslash Theta(1)$.{{harvtxt|Gusfield|1999}}, p.196.
• Search for a pattern P of length m with at most k mismatches in $O(k\; n\; +\; z)$ time, where z is the number of hits.{{harvtxt|Gusfield|1999}}, p.200.
• Find all $z$ maximal palindromes in $\backslash Theta(n)$,{{harvtxt|Gusfield|1999}}, p.198. or $\backslash Theta(g\; n)$ time if gaps of length $g$ are allowed, or $\backslash Theta(k\; n)$ if $k$ mismatches are allowed.{{harvtxt|Gusfield|1999}}, p.201.
• Find all $z$ tandem repeats in $O(n\; \backslash log\; n\; +\; z)$, and k-mismatch tandem repeats in $O(k\; n\; \backslash log\; (n/k)\; +\; z)$.{{harvtxt|Gusfield|1999}}, p.204.
• Find the longest common substrings to at least $k$ strings in $D$ for $k=2,\backslash dots,K$ in $\backslash Theta(n)$ time.{{harvtxt|Gusfield|1999}}, p.205.
• Find the longest palindromic substring of a given string (using the generalized suffix tree of the string and its reverse) in linear time.{{harvtxt|Gusfield|1999}}, pp.197–199.

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. Primary applications include:{{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}}

• 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.First introduced by {{harvtxt|Zamir|Etzioni|1998}}.

If each node and edge can be represented in $\backslash Theta(1)$ space, the entire tree can be represented in $\backslash Theta(n)$ space. The total length of all the strings on all of the edges in the tree is $O(n^2)$, but each edge can be stored as the position and length of a substring of {{mvar|S}}, giving a total space usage of $\backslash Theta(n)$ computer words. The worst-case space usage of a suffix tree is seen with a fibonacci word, giving the full $2n$ 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 {{mvar|σ}} be the size of the alphabet. Then you have the following costs:{{citation needed|date=October 2024}}

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 in good implementations. The suffix array reduces this requirement to a factor of 8 (for array including LCP values built within 32-bit address space and 8-bit characters.) This factor depends on the properties and may reach 2 with usage of 4-byte wide characters (needed to contain any symbol in some UNIX-like systems, see wchar_t) on 32-bit systems.{{citation needed|date=October 2024}} Researchers have continued to find smaller indexing structures.

Various parallel algorithms to speed up suffix tree construction have been proposed.{{sfnp|Apostolico|Iliopoulos|Landau|Schieber|1988}}{{sfnp|Hariharan|1994}}{{sfnp|Sahinalp|Vishkin|1994}}{{sfnp|Farach|Muthukrishnan|1996}}{{sfnp|Iliopoulos|Rytter|2004}}

Recently, a practical parallel algorithm for suffix tree construction with $O(n)$ work (sequential time) and $O(\backslash log^2\; n)$ span has been developed. The algorithm achieves good parallel scalability on shared-memory multicore machines and can index the human genome – approximately 3GB – in under 3 minutes using a 40-core machine.{{sfnp|Shun|Blelloch|2014}}

Though linear, the memory usage of a suffix tree is significantly higher

than the actual size of the sequence collection. For a large text,

construction may require external memory approaches.

There are theoretical results for constructing suffix trees in external

memory.

The algorithm by {{harvtxt|Farach-Colton|Ferragina|Muthukrishnan|2000}}

is theoretically optimal, with an I/O complexity equal to that of sorting.

However the overall intricacy of this algorithm has prevented, so far, its

practical implementation.{{sfnp|Smyth|2003}}

On the other hand, there have been practical works for constructing

disk-based suffix trees

which scale to (few) GB/hours.

The state of the art methods are TDD,{{harvtxt|Tata|Hankins|Patel|2003}}.

TRELLIS,{{harvtxt|Phoophakdee|Zaki|2007}}.

DiGeST,{{harvtxt|Barsky|Stege|Thomo|Upton|2008}}.

and

B²ST.{{harvtxt|Barsky|Stege|Thomo|Upton|2009}}.

TDD and TRELLIS scale up to the entire human genome resulting in a disk-based suffix tree of a size in the tens of gigabytes. However, these methods cannot handle efficiently collections of sequences exceeding 3 GB. DiGeST performs significantly better and is able to handle collections of sequences in the order of 6 GB in about 6 hours.

All these methods can efficiently build suffix trees for the case when the

tree does not fit in main memory,

but the input does.

The most recent method, B²ST, scales to handle

inputs that do not fit in main memory. ERA is a recent parallel suffix tree construction method that is significantly faster. ERA can index the entire human genome in 19 minutes on an 8-core desktop computer with 16 GB RAM. On a simple Linux cluster with 16 nodes (4 GB RAM per node), ERA can index the entire human genome in less than 9 minutes.{{sfnp|Mansour|Allam|Skiadopoulos|Kalnis|2011}}

• Suffix automaton

{{Reflist|colwidth=30em}}

• {{citation

| isbn=0-201-00029-6

| last1 = Aho | first1=Alfred V. | author1-link = Alfred Aho

| last2 = Hopcroft | first2=John E. | author2-link = John Hopcroft

| last3 = Ullman | first3= Jeffrey D. | author3-link = Jeffrey Ullman

| title=The Design and Analysis of Computer Algorithms

| location=Reading/MA

| publisher=Addison-Wesley

| year=1974| bibcode = 1974daca.book.....A }}.

• {{citation

| last1 = Apostolico | first1 = A.

| last2 = Iliopoulos | first2 = C.

| last3 = Landau | first3 = G. M.

| last4 = Schieber | first4 = B.

| last5 = Vishkin | first5 = U.

| title = Parallel construction of a suffix tree with applications

| journal = Algorithmica

| url = http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1617&context=cstech

| volume = 3

| issue = 1–4

| pages = 347–365

| year = 1988

| doi = 10.1007/bf01762122| s2cid = 5024136

}}.

• {{citation

| last1 = Baeza-Yates | first1 = Ricardo A. | author1-link = Ricardo Baeza-Yates

| last2 = Gonnet | first2 = Gaston H. | author2-link = Gaston Gonnet

| doi = 10.1145/235809.235810

| issue = 6

| journal = Journal of the ACM

| pages = 915–936

| title = Fast text searching for regular expressions or automaton searching on tries

| volume = 43

| year = 1996| s2cid = 1420298 | doi-access = free

}}.

• {{citation

| last1 = Barsky | first1 = Marina

| last2 = Stege | first2 = Ulrike

| last3 = Thomo | first3 = Alex

| last4 = Upton | first4 = Chris

| contribution = A new method for indexing genomes using on-disk suffix trees

| location = New York, NY, USA

| pages = 649–658

| publisher = ACM

| title = CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management

| year = 2008

| url = http://webhome.cs.uvic.ca/~thomo/papers/cikm08suffixtrees.pdf}}.

• {{citation

| last1 = Barsky | first1 = Marina

| last2 = Stege | first2 = Ulrike

| last3 = Thomo | first3 = Alex

| last4 = Upton | first4 = Chris

| contribution = Suffix trees for very large genomic sequences

| location = New York, NY, USA

| publisher = ACM

| title = CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management

| year = 2009

| url = http://csci.viu.ca/~barskym/publications/CIKMconference2008.pdf}}.

• {{citation |last=Farach |first=Martin |author-link=Martin Farach-Colton |title=38th IEEE Symposium on Foundations of Computer Science (FOCS '97) |pages=137–143 |contribution=Optimal Suffix Tree Construction with Large Alphabets |contribution-url=https://users.cs.utah.edu/~pandey/courses/cs6968/spring23/papers/optsuffixtree.pdf |year=1997 |title-link=Symposium on Foundations of Computer Science}}.
• {{citation

| last1 = Farach | first1 = Martin | author1-link = Martin Farach-Colton

| last2 = Muthukrishnan | first2 = S. | author2-link = S. Muthukrishnan (computer scientist)

| title = International Colloquium on Automata Languages and Programming

| contribution = Optimal Logarithmic Time Randomized Suffix Tree Construction

| year = 1996

| url = https://people.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf}}.

• {{citation

| last1 = Farach-Colton | first1 = Martin | author1-link = Martin Farach-Colton

| last2 = Ferragina | first2 = Paolo

| last3 = Muthukrishnan | first3 = S. | author3-link = S. Muthukrishnan (computer scientist)

| doi = 10.1145/355541.355547

| issue = 6

| journal = Journal of the ACM

| pages = 987–1011

| title = On the sorting-complexity of suffix tree construction.

| volume = 47

| year = 2000| s2cid = 8164822 | doi-access = free

}}.

• {{citation

|last1 = Giegerich

|first1 = R.

|last2 = Kurtz

|first2 = S.

|doi = 10.1007/PL00009177

|issue = 3

|journal = Algorithmica

|pages = 331–353

|title = From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction

|url = http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf

|volume = 19

|year = 1997

|s2cid = 18039097

|access-date = 2012-07-13

|archive-url = https://web.archive.org/web/20160303223209/http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf

|archive-date = 2016-03-03

|url-status = dead

}}.

• {{citation

| last = Gusfield | first = Dan

| isbn = 0-521-58519-8

| publisher = Cambridge University Press

| title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology

| year = 1997}}.

• {{citation

| last = Hariharan | first = Ramesh

| contribution = Optimal Parallel Suffix Tree Construction

| title = ACM Symposium on Theory of Computing

| year = 1994|url=https://www.sciencedirect.com/science/article/pii/S0022000097914963/pdf?md5=cf7ddbddc821ab41ef268fb03f6bdbaf&pid=1-s2.0-S0022000097914963-main.pdf}}.

• {{citation

| last1 = Iliopoulos | first1 = Costas

| last2 = Rytter | first2 = Wojciech

| contribution = On Parallel Transformations of Suffix Arrays into Suffix Trees

| title = 15th Australasian Workshop on Combinatorial Algorithms

| year = 2004

| citeseerx = 10.1.1.62.6715

}}.

• {{citation

| last1 = Mansour | first1 = Essam

| last2 = Allam | first2 = Amin

| last3 = Skiadopoulos | first3 = Spiros

| last4 = Kalnis | first4 = Panos

| issue = 1

| journal = Proceedings of the VLDB Endowment

| pages = 49–60

| title = ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings

| url = http://www.vldb.org/pvldb/vol5/p049_essammansour_vldb2012.pdf

| volume = 5

| year = 2011 | doi=10.14778/2047485.2047490| bibcode = 2011arXiv1109.6884M

| arxiv = 1109.6884

| s2cid = 7582116

}}.

• {{citation

| last = McCreight | first = Edward M. | author-link = Edward M. McCreight

| doi = 10.1145/321941.321946

| issue = 2

| journal = Journal of the ACM

| pages = 262–272

| title = A Space-Economical Suffix Tree Construction Algorithm

| citeseerx = 10.1.1.130.8022

| volume = 23

| date = 1976| s2cid = 9250303 }}.

• {{citation

| last1 = Phoophakdee | first1 = Benjarath

| last2 = Zaki | first2 = Mohammed J.

| contribution = Genome-scale disk-based suffix tree indexing

| location = New York, NY, USA

| pages = 833–844

| publisher = ACM

| title = SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data

| year = 2007

| citeseerx = 10.1.1.81.6031

}}.

• {{citation

| last1 = Sahinalp | first1 = Cenk

| last2 = Vishkin | first2 = Uzi

| contribution = Symmetry breaking for suffix tree construction

| title = ACM Symposium on Theory of Computing

| year = 1994

| pages = 300–309

| doi = 10.1145/195058.195164

| s2cid = 5985171

| doi-access = free

| isbn = 0-89791-663-8

}}

• {{citation

| last = Smyth | first = William

| publisher = Addison-Wesley

| title = Computing Patterns in Strings

| year = 2003}}.

• {{citation

| last1 = Shun | first1 = Julian

| last2 = Blelloch | first2 = Guy E.

| title = A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction

| journal = ACM Transactions on Parallel Computing

| volume = 1

| pages = 1–20

| year = 2014| doi = 10.1145/2661653

| s2cid = 1912378

}}.

• {{citation

| last1 = Tata | first1 = Sandeep

| last2 = Hankins | first2 = Richard A.

| last3 = Patel | first3 = Jignesh M.

| contribution = Practical Suffix Tree Construction

| pages = 36–47

| publisher = Morgan Kaufmann

| title = VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases

| year = 2003

| url = http://www.vldb.org/conf/2004/RS1P3.PDF}}.

• {{citation

| last = Ukkonen | first = E.

| doi = 10.1007/BF01206331

| issue = 3

| journal = Algorithmica

| pages = 249–260

| title = On-line construction of suffix trees

| url = http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

| volume = 14

| year = 1995| s2cid = 6027556

}}.

• {{citation

| last = Weiner

| first = P.

| contribution = Linear pattern matching algorithms

| doi = 10.1109/SWAT.1973.13

| pages = 1–11

| title = 14th Annual IEEE Symposium on Switching and Automata Theory

| contribution-url = http://airelles.i3s.unice.fr/files/Weiner.pdf

| year = 1973

| title-link = Symposium on Foundations of Computer Science

| access-date = 2015-04-16

| archive-date = 2016-03-03

| archive-url = https://web.archive.org/web/20160303211939/http://airelles.i3s.unice.fr/files/Weiner.pdf

| url-status = dead

}}.

• {{citation

| last1 = Zamir | first1 = Oren

| last2 = Etzioni | first2 = Oren

| author-link2=Oren Etzioni

| contribution = Web document clustering: a feasibility demonstration

| location = New York, NY, USA

| pages = 46–54

| publisher = ACM

| title = SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval

| year = 1998

| citeseerx = 10.1.1.36.4719

}}.

• [http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm Suffix Trees] by Sartaj Sahni
• [https://web.archive.org/web/20161104005610/https://xlinux.nist.gov/dads/HTML/suffixtree.html NIST's Dictionary of Algorithms and Data Structures: Suffix Tree]
• [http://www.balkenhol.net/papers/t1043.pdf.gz Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice], application of suffix trees in the BWT
• [http://www.cs.helsinki.fi/group/suds/ Theory and Practice of Succinct Data Structures], C++ implementation of a compressed suffix tree
• Ukkonen's Suffix Tree Implementation in C [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-1/ Part 1] [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-2/ Part 2] [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-3/ Part 3] [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-4/ Part 4] [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-5/ Part 5] [http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-6/ Part 6]
• [https://brenden.github.io/ukkonen-animation/ Online Demo: Ukkonen's Suffix Tree Visualization]

{{CS-Trees}}

{{Strings}}

{{DEFAULTSORT:Suffix Tree}}

Category:Trees (data structures)

Category:Substring indices

Category:String data structures

Category:Computer science suffixes