A compressed trie holding every suffix of a string, built so that any substring of the original string can be located in time proportional to the substring's own length; used in fast string search, genome analysis and data compression.
Facts
Core PrincipleCompresses all suffixes of a string into a single trie whose paths and stored positions let many string queries, such as substring search, run in time linear in the pattern length. 1 Connections
Sources
1. Wikipedia: Suffix Tree
Wikimedia FoundationHistory section, first sentence
The concept was first introduced by Weiner (1973).
Lead section, first sentence
a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.